洛谷 P1351 联合权值
JDOJ 2886: [NOIP2014]联合权值 D1 T2
Description
无向连通图 G有 n个点，n-1条边。点从 1到 n依次编号，编号为 i的点的权值为 Wi，每条边的长度均为 1。图上两点 (u, v)的距离定义为 u点到 v点的最短距离。对于图 G上的点对(u, v)，若它们的距离为 2，则它们之间会产生Wu×Wv的联合权值。
请问图 G上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
Input
第一行包含 1个整数 n。
接下来 n-1行，每行包含 2个用空格隔开的正整数 u、v，表示编号为 u和编号为 v的点之间有边相连。
最后 1行，包含 n个正整数，每两个正整数之间用一个空格隔开，其中第 i个整数表示图 G上编号为 i的点的权值为 Wi。
Output
输出共 1行，包含 2个整数，之间用一个空格隔开，依次为图 G上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对 10007取余。
Sample Input
5 1 2 2 3 3 4 4 5 1 5 2 3 10
Sample Output
20 74
HINT
【样例说明】
本例输入的图如上所示，距离为 2的有序点对有(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、(5,3)。其联合权值分别为 2、15、2、20、15、20。其中最大的是 20，总和为 74。
【数据说明】
对于 30%的数据，1< n ≤100；
对于 60%的数据，1< n ≤2000；
对于 100%的数据，1< n ≤200,000，0< Wi ≤10,000。
标签给的LCA，纯属P话。
这题不需要LCA的过程。根据题面，这是一棵树。
保证了没有环。
然后呢？我们就能发现，距离为2的点会有联合权值，那么我们就可以断定，这两个点是连在一个父亲节点上的。
然后我们就可以得出枚举的大致思路。
先枚举每个点，枚举它的所有出边，记录最大值和次大值，这个最大值和次大值之积就是第一问的解。
比较麻烦的是第二问。
它需要累加联合权值，这个temp是每次枚举到一个节点的时候的中转值，它需要累加权值，最后的temp就是这个父亲节点所能拼凑出的所有联合权值的值，然后累加ans2，注意取模。
最后还有答案的特殊处理。
就这样AC吧
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod=1e4+7;
int n,ans1,ans2;
int tot,to[400001],nxt[400001],head[200001],w[200001];
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
{
int max1=0,max2=0;
int temp=0;
for(int j=head[i];j;j=nxt[j])
{
int y=to[j];
if(w[y]>max1)
{
max2=max1;
max1=w[y];
}
else if(w[y]>max2)
max2=w[y];
ans2=(ans2+temp*w[y])%mod;
temp=(temp+w[y])%mod;
}
ans1=max(ans1,max1*max2);
}
printf("%d %d",ans1,(ans2*2)%mod);
return 0;
}