1351 联合权值

1351 联合权值

联合的权值最大是多少，权值之和最大是多少，动态规划，加上LCA，这是怕不是一个树形DP吧
如是联合两个点距离是2，那么就得需要中间点，所以我们需要枚举中间点
如果存在一个中间点，它的周围有两个点，权值分别为a，b则联合权值为2ab=(a+b)²-a(a²+b²)
如果中间点的周围有三个点，权值为a，b，c那么联合权值为2ab+2bc+2ac=(a+b+c)²-(a²+b²+c²)
综上所述，以某个节点为中转点的联合权值之和等于权值和的平方减去权值的平方和
为了找到最大的联合权值，只需要找到周围最大权值，相乘之后判断就好了
虽然题目让%10007，但是最大联合权值千万不能这样，为了防止负数，需要加上10007
啊啊啊啊

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZE=2e6+5;
int n;
int tot;
int maxx;
int ans;
int head[SIZE];
int w[SIZE];
struct node{
	int next;
	int to;
}e[SIZE];
void add(int u,int v)
{
	e[++tot].next=head[u];
	e[tot].to=v;
	head[u]=tot;
}
int main()
{
	memset(head,0,sizeof(head));
	cin>>n;
	for(int i=1;i<n;i++)//n-1条边 
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	
	for(int i=1;i<=n;i++)
	{
		cin>>w[i];
	}
	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)
		{
			/*cout<<j<<endl;
			return 0;*/
			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])%10007;
			t2=(t2+w[e[j].to]*w[e[j].to])%10007;
		}
		t1=t1*t1%10007;
		ans=(ans+t1+10007-t2)%10007;
		if(maxx<max1*max2) maxx=max1*max2;
	}
	cout<<maxx<<" "<<ans;
	return 0;
}