P1351

我的代码（$70$ 分，TLE了#$2$，#$9$，#$10$）：

#include<bits/stdc++.h>
#define ci int
#define cll long long
#define cull unsigned long long
#define cus unsigned short
#define cb bool
#define cd double
#define cf float
#define cs string
#define cc char
#define r0 return 0
#define in cin
#define out cout
using namespace std;
cll n,f[200010],nxt[200010],to[200010],num,w[200010],mh=0,sumh;
void add(ci a,ci b){
	to[++num]=b;
	nxt[num]=f[a];
	f[a]=num;
}
void tree(ci u){
	cll sum=0,c1=0,c2=0;
	for(ci i=f[u];i;i=nxt[i]){
		ci tp=to[i];
		if(w[tp]>c1){
			c2=c1;
			c1=w[tp];
		}
		else if(w[tp]>c2){
			c2=w[tp];
		}
		sumh=(sumh+sum*w[tp])%10007;
		sum=(sum+w[tp])%10007;
	}
	mh=max(mh,c1*c2);
}
int main(){
	in>>n;
	for(ci i=1;i<n;i++){
		ci x,y;
		in>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(ci i=1;i<=n;i++){
		in>>w[i];
	}
	for(ci i=1;i<=n;i++){
		tree(i);
	}
	out<<mh<<' '<<(sumh*2)%10007<<endl;
	r0;
}

另一位的AC代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=2e5+5,mo=10007;
struct cs{int to,nxt;}a[N*2];
int head[N],ll,v[N];
int n,ans,x,y,maxans;
void init(int x,int y){
    a[++ll].to=y;
    a[ll].nxt=head[x];
    head[x]=ll;
}
void work(int x){
    int sum=0,ma=0,m=0;
    for(int k=head[x];k;k=a[k].nxt){
        if(v[a[k].to]>ma){
			m=ma;
			ma=v[a[k].to];
		}
		else if(v[a[k].to]>m)m=v[a[k].to];
        ans=(ans+sum*v[a[k].to])%mo;
        sum=(sum+v[a[k].to])%mo;
    }
    maxans=max(maxans,ma*m);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        init(x,y);
		init(y,x);
    }
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)work(i);
    printf("%d %d",maxans,(ans*2)%mo);
}

求大佬帮忙指点一下时间复杂度哪里有区别？谢谢。