题目
无向连通图G 有n 个点，n - 1 条边。点从1 到n 依次编号，编号为 i 的点的权值为W i ，每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ，若它们的距离为2 ，则它们之间会产生Wu×Wv 的联合权值。
请问图G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
分析
70分：利用邻接表，强行找相隔的一个点。
100分：观察一下，题目给的是一棵树。距离相差为1可以转化为一个父亲的两个儿子。
假如一个根有三个儿子a,b,c。那么他们的权值和=a*b+b*a+a*c+c*a+b*c+c*b=(a+b+c)^2-a^2-b^2-c^2。
只要统计出以每个点为根儿子权值的和，进行一下处理就可以过了。
代码
#include<cstdio>
using namespace std;
#define inf 2147483646
#define to e[i].v
#define ll long long
#define M 10007
#define N 200010
struct node{ll v,next;}e[N*2];
ll head[N*2],vis[N],a[N],size[N];
ll id,n,mx,sum;
ll read()
{
ll x=0,f=1; char ch=getchar();
for (;ch>'9' || ch<'0';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0' && ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*f;
}
void swap(ll &a,ll &b) {ll t=a; a=b; b=t;}
ll max(ll a,ll b) {return a>b? a:b;}
ll min(ll a,ll b) {return a>b? b:a;}
void add(ll u,ll v) {e[id].v=v; e[id].next=head[u]; head[u]=id++;}
int main()
{
n=read(); id=1; mx=0;
for (ll i=1;i<n;i++)
{
ll u=read(),v=read();
add(u,v); add(v,u);
}
for (ll i=1;i<=n;i++) a[i]=read();
for (ll u=1;u<=n;u++)
{
ll max1=0,max2=0;
for (ll i=head[u];i;i=e[i].next)
{
size[u]=(size[u]+a[to])%M;
vis[to]++;
if (a[to]>max1) {max2=max(max1,max2); max1=a[to]; continue;}
max2=max(a[to],max2);
}
mx=max(mx,max1*max2);
}
sum=0;
for (ll i=1;i<=n;i++)
{
sum=(sum+size[i]*size[i]%M)%M;
sum=(sum-((a[i]*a[i])%M)*vis[i]%M+M)%M;
}
printf("%lld %lld",mx,sum);
return 0;
}
