联合权值

题目连接：

Description

给一棵树，然后每相距离为2的点都会产生一个联合权值，等于Wa*Wb

问你联合权值最大的是多少，所有联合权值的和是多少

Input

第一行n

n-1行 x y 表示xy连一条距离为1的边

n个数，表示每个点的权值

Output

最大值，和

Sample Input

5

1 2

2 3

3 4

4 5

1 5 2 3 10

Sample Output

20 74

Hint

题意：

题解

ans1 很显然等于某个点的最大的儿子乘以次大的儿子

ans2 = w[x] * (sum[fa[x]] - w[x]),fa[x]指的是父亲节点，但是这样会重复计算，所以直接按照dfs序去跑，计算过的就删去就好了

代码

#include
    
     using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}vector
     
       E[200100];int w[200100];int ans1;long long ans2;const int mod = 10007;int sum[200010];int max1[200010],max2[200010];void dfs(int x,int pre){    if(pre>0)    {        sum[pre]-=w[x];        ans2 = ans2 + 2LL*w[x]*sum[pre];        if(ans2>=mod)ans2%=mod;    }    for(int i=0;i
      
       max1[i])            {                max2[i]=max1[i];                max1[i]=w[v];            }            else if(w[v]==max1[i])                max2[i]=w[v];            else if(w[v]>max2[i])                max2[i]=w[v];        }        ans1 = max(ans1,max2[i]*max1[i]);    }    dfs(1,-1);    cout<
       
        <<" "<
        
         <