突然发现有一道题还没做。。。
这道题数据范围是200000，枚举一下中间夹的那个点，然后随便操作一下（看代码）就行了。
#include <iostream> #include <cstdio> #include <cstring> const int N=200005,mod=10007; using namespace std; int n,head[N],nxt[N<<1],to[N<<1],val[N],mx,ans,ecnt; inline void add(int bg,int ed) {nxt[++ecnt]=head[bg];to[ecnt]=ed;head[bg]=ecnt;} inline void ins(int a,int b) {add(a,b),add(b,a);} inline void sear(int now) { int sum=0,Max=0; for(int i=head[now];i;i=nxt[i]) { if(val[to[i]]*Max>mx) mx=val[to[i]]*Max; if(val[to[i]]>Max) Max=val[to[i]]; ans=(ans+val[to[i]]*sum)%mod; sum=(sum+val[to[i]])%mod; } } int main() { scanf("%d",&n); for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),ins(x,y); for(int i=1;i<=n;i++) scanf("%d",&val[i]); for(int i=1;i<=n;i++) sear(i); cout<<mx<<' '<<(ans*2)%mod<<endl; return 0; }