题目传送门
日常水一水，挑一道Noip的水题来练练手。
这题的题意是求一棵树上所有的由两条边相连的点对的点权积的和，还有点权积的最大值。
我们可以单独挑出一个点i，假设有4个点v1,v2,v3,v4和它直接相连，那么第i号节点对点权积和的贡献S可以表示成：
S=W(v1)*W(v2)+W(v1)*W(v3)+W(v1)*W(v4)+W(v2)*W(v3)+W(v2)*W(v4)+W(v3)*W(v4)
把右边的式子变形一下，得：S=W(v2)*W(v1)+W(v3)*(W(v1)+W(v2))+W(v4)*(W(v1)+W(v2)+W(v3))
这下就好办了，我们可以枚举所有节点i，然后枚举所有与第i号节点直接相连的节点j，k表示之前枚举的和第i号节点直接相连的节点，那么ans+=W(j)*ΣW(k)。
求点权积的最大值，这个嘛，就不用我说了吧。
附上AC代码：
#include <cstdio> #define p 10007 #define N 200010 using namespace std; struct side{ int to,nt; }s[N<<1]; int n,x,y,ans,num,h[N],a[N],mx1,mx2,sum,mx; inline void add(int x,int y){ s[++num]=(side){y,h[x]},h[x]=num; s[++num]=(side){x,h[y]},h[y]=num; } inline int max(int a,int b){return a>b?a:b;} int main(void){ scanf("%d",&n); for (int i=1; i<n; ++i) scanf("%d%d",&x,&y),add(x,y); for (int i=1; i<=n; ++i) scanf("%d",&a[i]); for (int i=1; i<=n; ++i){ sum=mx1=mx2=0; for (int j=h[i]; j; j=s[j].nt){ ans=(ans+sum*a[s[j].to])%p,sum=(sum+a[s[j].to])%p; if (a[s[j].to]>=mx1) mx2=mx1,mx1=a[s[j].to]; else if (a[s[j].to]>mx2) mx2=a[s[j].to]; } mx=max(mx,mx1*mx2); } printf("%d %d",mx,(ans<<1)%p); return 0; }