「题解」Luogu 1351「联合权值」

分析

按照LCA的思想就可以得到以下做法

代码

#include<cstdio>
#include<vector>
#include<algorithm>
typedef long long int64;
const int MAXN = 200000 + 6,MOD = 10007,INF = 0x3f3f3f3f;
int64 W[MAXN];
std::vector<int> G[MAXN];
inline void addEdge(int u,int v){G[u].push_back(v);}
int main(){
    int n,u,v;scanf("%d",&n);
    int64 delta,delta1,delta2,max = -INF,sum = 0;
    for(int i = 1;i < n;i++){
        scanf("%d %d",&u,&v);
        addEdge(u,v),addEdge(v,u);
    }
    for(int i = 1;i <= n;i++) scanf("%lld",&W[i]);
    for(int i = 1;i <= n;i++){
        delta2 = delta1 = 0;
        for(int j = 0;j < G[i].size();j++){
            delta = W[G[i][j]] * delta2;
            max = std::max(max,W[G[i][j]] * delta1);
            delta1 = std::max(delta1,W[G[i][j]]);
            sum += delta % MOD;
            sum %= MOD;
            delta2 += W[G[i][j]];
        }
    }
    printf("%lld %lld",max,sum * 2 % MOD);

    return 0;
}