NOIp2014 T2联合权值

背景

NOIP2014提高组第二题

描述

无向连通图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。

输入样例：

1 2

2 3

3 4

4 5

1 5 2 3 10

输出格式

输出文件名为link.out。

输出共1行，包含2个整数，之间用一个空格隔开，依次为图G上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对10007取余。

输出样例：

20 74

备注

对于30%的数据，1<n≤100；

对于60%的数据，1<n≤2000；

对于100%的数据，1<n≤200,000，0<Wi ≤10,000。

首先观察数据发现60%的数据是可以直接过的。

进一步，在模拟数据的时候不难发现可以用树形dp做：

1、提出一个点来作为根

2、记录每个点的父亲以及孩子

3、对于有两个及以上的孩子，任意两个孩子到该点的距离为2，对此进行(a+b)^2-(a^2+b^2)的运算

4、对于有父亲的呢节点，直接计算sum_son与value[father]的乘积的2倍。

一年不写的code:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MOD = 10007;
const int N = 200010;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,l,r) for(int i=l;i<=r;i++)

struct Edge{
    int s,t,next;
}E[N*2];

int ansmax,First,Second,es,n,cnt[N],value[N],ans,sonsqr[N],son[N],father[N],head[N];
bool vis[N];

void makelist(int s,int t){
    E[es].s=s;E[es].t=t;
    E[es].next=head[s];head[s]=es++;
}

int Dfs(int s,int fa){
    int p=head[s];vis[s]=true;
    int First=value[fa],Second=0;
    while(p!=-1){
        int t=E[p].t;
        if(!vis[t]){
            sonsqr[s]=(sonsqr[s]+(value[t]*value[t])%MOD)%MOD;
            son[s]=(son[s]+value[t])%MOD;cnt[s]++;
            if(value[t]>First) Second=First,First=value[t];
            else  if(value[t]>Second) Second=value[t];
            Dfs(t,s);
        }
        p=E[p].next;
    }
    father[s]=fa;
    ansmax=max(ansmax,First*Second);
}

int main(){
    freopen("link.in","r",stdin);
    freopen("link.out","w",stdout);
    memset(head,-1,sizeof(head));
    scanf("%d",&n);int x,y;
    For(i,n-1){
        scanf("%d%d",&x,&y);
        makelist(x,y);makelist(y,x);
    }
    For(i,n) {
        scanf("%d",&value[i]);
        value[i]%=MOD;
    }
    Dfs(1,0);
    For(s,n){
        if(cnt[s]>1){
            int ans1=son[s]%MOD,ans1sqr=sonsqr[s]%MOD;
            ans=(ans+(ans1*ans1-ans1sqr)%MOD)%MOD;
        }
        if(father[s]!=0){
            ans=(ans+son[s]*value[father[s]]*2)%MOD;
        }
    }
    printf("%d %d
",ansmax,(ans+MOD)%MOD);
    return 0;
}

Dfs版