题目链接:https://www.luogu.com.cn/problem/P1351
有n个点,n-1条边,所以是一个无根树。而两点之间的距离为2,所以两点之间有一个中转点,这道题的关键就是枚举这个中转点,而不是两个顶点。
这样每次枚举一个中转点,便枚举与它相邻的所有点,记录下其中最大的、次大的两个点的权值。扫完一遍后最大的和次大的乘积即为答案。
一个中转点的权值和,即2*w1*w2,那么就可以看成$(w_1+w_2)^2-(w_1^2+w_2^2)$,如果有多个点(>=2),也是一样的。都是和的平方减去平方的和。
AC代码:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 typedef long long ll; 6 const int N=200005; 7 const int mod=10007; 8 int n,tot; 9 ll maxx,max1,max2,t1,t2,ans; 10 int head[N],w[N]; 11 struct node{ 12 int to,next; 13 }edge[N<<1]; 14 void add(int u,int v){ 15 edge[tot].to=v; 16 edge[tot].next=head[u]; 17 head[u]=tot++; 18 } 19 void DFS(){ 20 for(int i=1;i<=n;i++){ 21 max1=max2=0,t1=t2=0; 22 for(int j=head[i];j!=-1;j=edge[j].next){ 23 int v=edge[j].to; 24 if(w[v]>max1) max2=max1,max1=w[v]; 25 else if(w[v]>max2) max2=w[v]; 26 t1=(t1+w[v])%mod; 27 t2=(t2+w[v]*w[v])%mod; 28 } 29 t1*=t1; 30 ans=(ans+t1+mod-t2)%mod; 31 maxx=max(maxx,max1*max2); 32 } 33 } 34 int main(){ 35 memset(head,-1,sizeof(head)); 36 scanf("%d",&n); 37 for(int i=1;i<n;i++){ 38 int u,v; 39 scanf("%d%d",&u,&v); 40 add(u,v); add(v,u); 41 } 42 for(int i=1;i<=n;i++) scanf("%d",&w[i]); 43 DFS(); 44 printf("%lld %lld",maxx,ans); 45 return 0; 46 }