LuoguP1351[NOIP2014] 联合权值 解题报告【树形DP】

题目描述
无向连通图G有n个点，n−1条边。点从1到n依次编号，编号为i的点的权值为Wi，每条边的长度均为1。图上两点(u,v)的距离定义为u点到v点的最短距离。对于图G 上的点对(u,v)，若它们的距离为2，则它们之间会产生Wu×Wv的联合权值。
请问图G上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
输入输出格式
输入格式：
输入文件名为link .in。
第一行包含1 个整数n。
接下来n−1行，每行包含 2 个用空格隔开的正整数u、v，表示编号为u和编号为v的点之间有边相连。
最后1 行，包含n个正整数，每两个正整数之间用一个空格隔开，其中第i个整数表示图G上编号为i的点的权值为Wi。
输出格式：
输出文件名为link .out 。
输出共1 行，包含2个整数，之间用一个空格隔开，依次为图G上联合权值的最大值
和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对10007取余。
输入输出样例
输入样例#1：
5
1 2
2 3
3 4
4 5
1 5 2 3 10
输出样例#1：
20 74
说明

本例输入的图如上所示，距离为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 。
解题报告
我们考虑什么样的点对满足距离等于2。一是一个点和他的爷爷，另一个是一个点的儿子节点中的两个。
我们重点考虑第二种情况的联合权值的计算。
联合权值的最大值一定等于最大点权*次大点权，因此更新最大值和次大值就好了。重点是怎样求和。
所谓联合权值的和，也就是一个点的所有儿子两两间的点权积，我们计算一个点权和：sumson=wson1+wson2+...+wsonk，再计算一个平方和summ=w2son1+w2son2+...+w2sonk，可以得出，这一个点的儿子们的和sum=sum2son−summ。
代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200000,mod=10007;
struct edge
{
    int v,next;
}ed[2*N+5];
int n,father[N+5];
int sum,vmax,w[N+5];
int head[N+5],num;
void build(int u,int v)
{
    ed[++num].v=v;
    ed[num].next=head[u];
    head[u]=num;
}
void dfs(int u,int f)
{
    int max_1=0,max_2=0,sum_son=0,sum_m=0;
    if(father[f])sum=(sum+w[u]*w[father[f]]*2%mod)%mod,vmax=max(vmax,w[u]*w[father[f]]);//之所以*2是因为他问的是点对
    for(int i=head[u];i!=-1;i=ed[i].next)
    {
        int v=ed[i].v;
        if(v==f)continue;
        father[v]=u;
        if(w[v]>max_1)max_1=w[v];
        else if(w[v]>max_2)max_2=w[v];
        sum_son=(sum_son+w[v])%mod;
        sum_m=(sum_m+w[v]*w[v]%mod)%mod;
        dfs(v,u);
    }
    sum=(sum+(sum_son*sum_son%mod-sum_m%mod+mod)%mod)%mod;
    vmax=max(vmax,max_1*max_2);
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        build(u,v);
        build(v,u);
    }
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    dfs(1,0);
    printf("%d %d",vmax,sum%mod);
    return 0;
}