为了写一写LCA，我就按照标签找……结果这道题我写完竟然没用LCA……真是神奇。。。
很多人（包括我），首先就想到了要枚举每一个点，再枚举任意这个点的两个儿子，可是显然O(n2)会T……
其实我们只要线性扫一遍就可以了，利用小学学到的乘法分配率，边走边加val，这样下一个点和val的乘积就是它和这之前所有的点的乘积之和，最后就是sum。
当然，点对反过来就是一组新的点对，所以，随后的sum要乘2。
而对于最大值，只要每一次更新我扫过的这些点权里最大的数是多少（在一次外层循环中），和新的点权相乘，看看能不能更新最大解即可。
对了，记得看看是给谁取模。
代码如下：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; #define maxn 4000000 #define mod 10007 #define int long long int head[maxn],to[maxn],nxt[maxn],w[maxn]; int n,cnt; void add(int a,int b) { to[++cnt]=b; nxt[cnt]=head[a]; head[a]=cnt; } main() { scanf("%lld",&n); for(int i=1;i<=n-1;i++) { int a,b; scanf("%lld%lld",&a,&b); add(a,b); add(b,a); } for(int i=1;i<=n;i++) scanf("%lld",&w[i]); int sum=0,Max=0; int fir,val,maxpo; for(int i=1;i<=n;i++) { fir=head[i]; val=w[to[fir]]%mod; maxpo=w[to[fir]]; fir=nxt[fir]; for(; fir; fir=nxt[fir]) { sum=(sum+val*w[to[fir]])%mod; val=(val+w[to[fir]])%mod; Max=max(Max,maxpo*w[to[fir]]); maxpo=max(maxpo,w[to[fir]]); } } printf("%lld %lld",Max,(2*sum)%mod); return 0; }
原文：https://www.cnblogs.com/popo-black-cat/p/10301580.html