[NOIP2014]联合权值

题目（vijos）
这题一开始稍微想复杂了......
其实思考一下就明白，距离为2的两个点之间一定有一个点（废话），
于是我们反过来想：连接在一个点上的不同的两个点一定距离为2。
所以，这题可以这样：
枚举每一个点，把连接在这个点上的点的权值用一个d数组记录下来。
然后对d数组从大到小排序，这样第一题就解决了：ans1=max(ans1,d[1]*d[2])。
第二问采用前缀和的方式解决：
比如连接在同一个点上的点的权值分别为1,3,5,6，
假设我们不考虑有序数对，那么总和为1*(3+5+6)+3*(5+6)+5*6，
明显可以用前缀和来优化。
答案为sum*2。
这题就解决了~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
template <class ___E> inline void read(___E &e)
{
	e=0;bool ck=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck) e = -e;
}
const int mod=10007;
struct edge{
	int vk;
	int next;
}e[400005];
int a[200005];
int d[200005];
int sum;
int maxn;
ll s[200005];
int n,m;
int head[200005],t=1;
bool cmp(const int &x,const int &y)
{
	return x>y;
}
void ad(int u,int v)
{
	e[t].vk=v;
	e[t].next=head[u];
	head[u]=t++;
}
int main()
{
	read(n);
	for (register int i=1;i<n;++i)
	{
		int x,y;
		read(x);
		read(y);
		ad(x,y);
		ad(y,x);
	}
	for (register int i=1;i<=n;++i)
	{
		read(a[i]);
	}
	int cnt=0;
	for (register int k=1;k<=n;++k)
	{
		for (int i=1;i<=cnt;++i)
		{
			d[i]=0;
			s[i]=0;
		}
		cnt=0;
		for (int i=head[k];i;i=e[i].next)
		{
			++cnt;
			int v=e[i].vk;
			d[cnt]=a[v];
		}
		if (cnt==1) continue;
		sort(d+1,d+cnt+1,cmp);
		maxn=max(maxn,d[1]*d[2]);
		for (int i=1;i<=cnt;++i)
			s[i]=s[i-1]+d[i];
		for (int i=1;i<cnt;++i)
		{
			sum=sum+(((d[i]%mod)*((s[cnt]-s[i])%mod))%mod);
			sum%=mod;
		}
	}
	printf("%d %d",maxn,(sum*2)%mod);
	return 0;
}