連立権―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; }