NOIP2014联合权值

枚举+乘法结合律

枚举每个点左右相邻的两个点乘积和，做(a+b+c...)(a+b+c...)的时候展开减掉a^2+b^2+c^2再除以2就是答案了

注意爆int取模

 1 #include<iostream>
 2 #include<cstdio>
 3 #define N 2000005
 4 using namespace std;
 5 struct node{
 6     long long u,v;
 7 }e[N];
 8 long long first[N],nxt[N],cnt,max0,ans,w[N];
 9 void add(long long u,long long v){
10     e[++cnt].u=u;
11     e[cnt].v=v;
12     nxt[cnt]=first[u];
13     first[u]=cnt;
14 } 
15 void sum(long long x){
16     long long s[200005],tot=0,num=0,maxv=0,tmaxv=0;
17     for(long long i=first[x];i;i=nxt[i]){
18         s[++tot]=e[i].v,num+=w[e[i].v];
19         num%=10007;
20         if(w[e[i].v]>maxv){
21             tmaxv=maxv;
22             maxv=w[e[i].v];
23         } 
24         else{
25             tmaxv=max(tmaxv,w[e[i].v]);
26         }
27     }
28     num%=10007;
29     max0=max(max0,maxv*tmaxv);
30     ans+=num*num%10007;
31     for(long long i=1;i<=tot;i++)
32         ans-=(w[s[i]]*w[s[i]])%10007;
33     if(ans<0)ans+=10007;
34     ans%=10007;
35 }
36 int main(){
37     //freopen("link.in","r",stdin);
38     //freopen("link.out","w",stdout);
39     ios::sync_with_stdio(false);
40     long long n;
41     cin>>n;
42     for(long long i=1;i<n;i++){
43         long long a,b;
44         cin>>a>>b;
45         add(a,b);
46         add(b,a);
47     }
48     for(long long i=1;i<=n;i++)cin>>w[i];
49     for(long long i=1;i<=n;i++)
50         sum(i);
51     cout<<max0<<" "<<ans;
52     return 0;
53 }