联合权值

题目大意:

你有一棵树,问你距离为二的节点的最大联合权值与联合权值和

分析

在巨佬的提示下得到了思路，这不就是枚举每个点作为中间点，再枚举儿子们。求一下最大值和权值和就好了啊。

#include<bits/stdc++.h>
#define ll long long
const int N=2e6+5,INF=0x3f3f3f3f,mod=10007;
using namespace std;

int n,cnt,ans,maxx;
int w[N],head[N];
struct node
{
    int to,next_;
}e[N<<1];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

void add(int u,int v)
{
    e[++cnt].next_=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}

int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int u,v;
        u=read();v=read();
        add(u,v);add(v,u);
    }
    for(int i=1;i<=n;i++) w[i]=read();
    for(int i=1;i<=n;i++)
    {
        int max1=0,max2=0;
        int t1=0,t2=0;
        for(int j=head[i];j;j=e[j].next_)
        {
            if(w[e[j].to]>max1)    max2=max1,max1=w[e[j].to];
            else if(w[e[j].to]>max2)    max2=w[e[j].to];
            t1=(t1+w[e[j].to])%mod;
            t2=(t2+w[e[j].to]*w[e[j].to])%mod;
        }
        t1=t1*t1%mod;
        ans=(ans+t1+mod-t2)%mod;
        if(maxx<max1*max2)maxx=max1*max2;
    }
    printf("%d %d\n",maxx,ans);
    return 0;
}