連立権―o(n)作り方
szjは図を保存していない方法を考えて、各頂点に関連する頂点の権利値とを保存しました.例えば、頂点1は、頂点a 1、a 2、a 3に関連する.第一条辺はa 1で、第二回はa 1*a 2で、第三回はa 3*(a 1+a 2)です.
#include
#include
#include
using namespace std;
const int MaxN=200000;
const int MOD=10007;
int n;
long long f[MaxN],t[MaxN];
long long value[MaxN],vs[MaxN];
long long sum[MaxN],Max[MaxN];
int main(){
scanf("%d",&n);
for(int i=1;i<=n-1;++i){
scanf("%lld%lld",f+i,t+i);
}
for(int i=1;i<=n;++i){
scanf("%lld",value+i);
}
long long ans1=0,ans2=0;
for(int i=1;i<=n-1;++i){
ans1=max(ans1,max(Max[f[i]]*value[t[i]],Max[t[i]]*value[f[i]]));//
ans2=(ans2+(value[f[i]]*sum[t[i]])+(value[t[i]]*sum[f[i]]));//
sum[f[i]]+=value[t[i]];
sum[t[i]]+=value[f[i]];
Max[f[i]]=max(Max[f[i]],value[t[i]]);
Max[t[i]]=max(Max[t[i]],value[f[i]]);
}
printf("%lld %lld
",ans1,2*ans2%MOD);
return 0;
}