联合权值

题目：https://ac.nowcoder.com/acm/problem/16495
解题报告：https://ac.nowcoder.com/acm/problem/blogs/16495

个人总结：

1. 题目的点是从1开始的，因此输入数据下表要从1开始，避免麻烦。
2. 首先不难看出如果要求联合权值和必须枚举所有能产生联合权值的情况。又因为产生联合权值的两点u,v中间肯定间隔一点i，并且我们发现如果以u或v为起点枚举情况的话其效率是很低的。因此我们需要枚举i，i是中点，连接中点的两个点一定会产生联合权值。
3. 数据过大，一对对算会超时，巧用公式。公式见题解。
4. 理解解题思路后不难，自己想想不到不超时的方法！还是多积累积累吧！

AC代码：

#include <iostream>
#include <algorithm>
#define mode 10007
#define maxn 200001
#define maxw 10000
#define LL long long 
using namespace std ;
struct node{
	LL max1 = 0 ,max2 =0 , sum1=0,sum2=0;
}datei[maxn];
LL date[maxn][2];
LL Pow[maxn];
int main ()
{
	int n;
	cin >> n ;
	for (int i=1;i<=n-1;i++)
		cin >>date[i][0]>>date[i][1];
	
	for (int i=1;i<=n;i++)
		cin >> Pow[i];
		
	
	for (int i=1;i<=n-1;i++)
	{
		LL P1 = date[i][0];
		LL P2 = date[i][1];
		LL pow1 = Pow[P1];
		LL pow2 = Pow[P2];
		
		datei[P1].sum1 += pow2 ;
		datei[P2].sum1 += pow1 ;
		datei[P1].sum2 += pow2*pow2;
		datei[P2].sum2 += pow1*pow1;
		
		if (pow1>datei[P2].max1)
		{
			datei[P2].max2 = datei[P2].max1 ;
			datei[P2].max1 = pow1 ;
		}
		else if (pow1 > datei[P2].max2)
			datei[P2].max2 = pow1 ;
	
		if (pow2>datei[P1].max1)
		{
			datei[P1].max2 = datei[P1].max1 ;
			datei[P1].max1 = pow2 ;
		}
		else if (pow2 > datei[P1].max2)
			datei[P1].max2 = pow2 ;
	}
	LL Sum = 0 ;
	LL Summax= - 100;

	for (int i=1 ; i<= n ;i++)
	{
		 Sum += datei[i].sum1*datei[i].sum1 - datei[i].sum2;
		 Sum %= mode;
		 Summax= max(datei[i].max1 * datei[i].max2 , Summax);
	}
		
	cout << Summax <<" "<<Sum ;
	return 0;
}