3728 联合权值[NOIP 2014 Day1 T2]

来源：NOIP2014 Day1 T2

OJ链接：

http://codevs.cn/problem/3728/

https://www.luogu.org/problemnew/show/P1351

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #define N 200010  
 4 #define P 10007  
 5 using namespace std;  
 6 struct use{int st,en;}e[N*2];  
 7 long long ans,w[N],maxx;  
 8 int cnt,n,a,b,point[N],next[N*2];  
 9 void add(int x,int y){  
10   next[++cnt]=point[x];point[x]=cnt;  
11   e[cnt].st=x;e[cnt].en=y;    
12 }  
13 int main(){  
14    scanf("%d",&n);  
15    for (int i=1;i<=n-1;i++){scanf("%d%d",&a,&b);add(a,b);add(b,a);}    
16    for (int i=1;i<=n;i++) scanf("%lld",&w[i]);  
17    for (int i=1;i<=n;i++){  
18      long long tp1(0),tp2(0),mx1(-1),mx2(-1);  
19      for (int j=point[i];j;j=next[j]){  
20        (tp1+=w[e[j].en])%=P;(tp2+=w[e[j].en]*w[e[j].en])%=P;      
21        if (mx1<w[e[j].en]){mx2=mx1;mx1=w[e[j].en];}  
22        else mx2=max(mx2,w[e[j].en]);  
23      }  
24      (ans+=(tp1*tp1)%P-tp2+P)%=P;maxx=max(maxx,mx1*mx2);  
25    }  
26    cout<<maxx<<' '<<ans<<endl;  
27 }