Luogu 1351 NOIP 2014 联合权值（贪心，计数原理）
Description
无向连通图 G 有 n 个点，n-1 条边。点从 1 到 n 依次编号，编号为 i 的点的权值为 Wi， 每条边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v)，若它们的距离为 2，则它们之间会产生Wu×Wv的联合权值。 请问图 G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
第一行包含 1 个整数 n。 接下来 n-1 行，每行包含 2 个用空格隔开的正整数 u、v，表示编号为 u 和编号为 v 的点 之间有边相连。 最后 1 行，包含 n 个正整数，每两个正整数之间用一个空格隔开，其中第 i 个整数表示 图 G 上编号为 i 的点的权值为Wi。
Output
输出共 1 行，包含 2 个整数，之间用一个空格隔开，依次为图 G 上联合权值的最大值 和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对10007取余。
5 1 2 2 3 3 4 4 5 1 5 2 3 10
Sample Output
20 74
Http
Luogu:https://www.luogu.org/problem/show?pid=1351
Source
贪心，计数原理
题目大意
给出一棵树，求任意距离为2的两点的点权之积的最大值和总和
解决思路
因为任意两个距离为2的点一定有一个中间点相连，所以我们可以考虑枚举中间那个点，然后将与这个点距离为1的点分别相乘，同时维护这些点中的最大值和次大值，方便求出最大积
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
const int maxN=200100;
const int Mod=10007;
const int inf=2147483647;
int n;
vector<int> E[maxN];
int W[maxN];
int main()
{
scanf("%d",&n);
for (int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
E[u].push_back(v);
E[v].push_back(u);
}
for (int i=1;i<=n;i++)
scanf("%d",&W[i]);
ll Ans=0;
ll maxW=0;//最大积
for (int i=1;i<=n;i++)
{
ll nowsum=0;//当前和
ll max1=0,max2=0;//最大值和次大值
for (int j=0;j<E[i].size();j++)
{
int v=E[i][j];
Ans=(Ans+nowsum*W[v]%Mod)%Mod;//运用计数原理计数
nowsum=(nowsum+W[v])%Mod;
if (W[v]>=max1)
{
max2=max1;
max1=W[v];
}
else
if (W[v]>max2)
max2=W[v];
}
maxW=max(maxW,max1*max2);//取最大积
}
cout<<maxW<<" "<<Ans*2%Mod<<endl;
return 0;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7625842.html
相关资源：JAVA上百实例源码以及开源项目
