这个应该结合图片 但我不会上传 5555
这是一道统计题 首先就找特征
很明显 我们可以想到枚中间点来做这个题
第一问很容易解决 找到wx*wy最大的就好了
我们通过菊花图可以发现一个定理
我们要求的是 2wab+2wbc+2wcd+2wda
(a+b+c+d)²=a²+b²+c²+d²+a(b+c+d)+b(a+c+d)+c(a+b+d)+d(a+b+c)
移项得
(a+b+c+d)²-a²+b²+c²+d²=2wab+2wbc+2wcd+2wda
这就是我们想要的答案
#include<cstdio>
using namespace std;
struct edge
{
int next;
int to;
}a[400005];
int edgenum,head[200005],w[200005];
int n,ans,maxx;
void add(int u,int v)//加入一条从u到v的边
{
a[++edgenum].next=head[u];
a[edgenum].to=v;
head[u]=edgenum;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
{
int max1=0,max2=0;//最大的两个权值
int t1=0,t2=0;//t1代表和的平方,t2代表平方和
for(int j=head[i];j;j=a[j].next)
{
if(w[a[j].to]>max1)max2=max1,max1=w[a[j].to];
else if(w[a[j].to]>max2)max2=w[a[j].to];
t1=(t1+w[a[j].to])%10007;
t2=(t2+w[a[j].to]*w[a[j].to])%10007;
}
t1=t1*t1%10007;
ans=(ans+t1+10007-t2)%10007;
if(maxx<max1*max2)maxx=max1*max2;
}
printf("%d %d\n",maxx,ans);
return 0;
}