曾经感觉非常难的题 现在一遍过了、、
主要是有前缀和的思想 和取最大值和次大值的乘积由小技巧；；
只保存一个最大值 ，和每个数*，直到这个最大值被更新。。
由于每次乘都是在1~当前这个数的最大值再乘这个数，所以如果它不是最大值，则一路统计了答案，如果是 ，则这个1~当前数的最大值必然是最优的次大值
码：
#include<iostream> #include<cstdio> using namespace std; #define N 200005 #include<vector> vector<int>v[N]; int x,y,i,n,j,w[N],ans,daan; int main() { scanf("%d",&n); for(i=1;i<n;i++) { scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } for(i=1;i<=n;i++)scanf("%d",&w[i]); for(i=1;i<=n;i++) { if(v[i].size()==1)continue; int lmax=0,qsum=0; for(j=0;j<v[i].size();j++) { ans=max(lmax*w[v[i][j]],ans); lmax=max(lmax,w[v[i][j]]); qsum+=w[v[i][j]]; qsum%=10007; } for(j=0;j<v[i].size();j++) { daan+=(w[v[i][j]]*(qsum-w[v[i][j]])); daan%=10007; } } printf("%d %d",ans,daan); }