题解 | #[NOIP2014]联合权值#

#include<bits/stdc++.h>
using namespace std;
const int mo=10007;
#define maxm 200010
#define ll long long
ll w[maxm];
vector<int>G[maxm];
struct node{
    ll v,sum1,sum2;
}f[maxm],ne[maxm];

void dfs(int u,int pr){
	vector<int>S;
	for(int i=0;i<(int)G[u].size();i++){
		int v=G[u][i];
		if(pr==v)continue;
        dfs(v,u);
		S.push_back(v);
        ne[u].sum1=(ne[u].sum1+w[v])%mo;
        ne[u].v=max(ne[u].v,w[v]);
        f[u].v=max(f[u].v,ne[v].v);
        f[u].sum1=(f[u].sum1+ne[v].sum1);
	}
    ll maxv=0;
    int sum=0;
    for(int i=0;i<S.size();i++){
        int v=S[i];
        f[v].sum2=(f[v].sum2+sum)%mo;
        f[v].v=max(f[v].v,maxv);
        sum=(sum+w[v])%mo;
        maxv=max(maxv,w[v]);
    }
    maxv=0;sum=0;
	for(int i=S.size()-1;i>=0;i--){
        int v=S[i];
        f[v].sum2=(f[v].sum2+sum)%mo;
        f[v].v=max(f[v].v,maxv);
        sum=(sum+w[v])%mo;
        maxv=max(maxv,w[v]);
    }
    
	
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(int i=1;i<=n;i++) cin>>w[i];
	dfs(1,0);
    ll maxv=0,sum=0;
	for(int i=1;i<=n;i++){
        maxv=max(maxv,w[i]*f[i].v);
        sum=(sum+f[i].sum1*2*w[i]+w[i]*f[i].sum2)%mo;
    }
    cout<<maxv<<' '<<sum;
	return 0;
}

这道题类似于树形dp

先求出每个点的最大联合权值以及每个点相关的权值对的和，然后max即可