P1351 [NOIP2014 提高组] 联合权值

原题链接

题解

树形dp的想法，递归返回的是子树的最大联合权值以及联合权值之和。

首先，根据题目意思可以知晓该无向图构成的是一棵树。

由树形dp的遍历可知，当我们来到 root结点时，其所有孩子结点的子树 最大联合权值 和 联合权值之和 都已经知晓，我们只需要对其取 max 和 累加 即可。

but，上面是以root结点为中转结点的情况，所以我们还要考虑root结点与 其父节点的父节点 相连形成的联合权值的情况，进行特判即可。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const ll mod=10007;
ll head[N],Next[N<<1],to[N<<1],w[N],cnt=1;
struct node{
    ll MAX_val,sum;
    node(ll MAX_val,ll sum): MAX_val(MAX_val),sum(sum){}
};

void build(int from,int to_){
    Next[cnt]=head[from];
    to[cnt]=to_;
    head[from]=cnt++;
}

node dfs(int root,int f,int g){
    int more=w[root]*w[g]*2;
    node ans(more/2,0);
    ans.sum=(ans.sum+more)%mod;
     
    node x(0,0);
    ll max1=0,max2=0,val=0,power=0;
    for (int i=head[root];i>0;i=Next[i]){
        if (to[i]==f) continue;
        val+=w[to[i]];
        power+=w[to[i]]*w[to[i]];
        x=dfs(int(to[i]),root,f);
        ans.sum=(ans.sum+x.sum)%mod;
        ans.MAX_val=max(ans.MAX_val,x.MAX_val);
        if (w[to[i]]>max1) max1=w[to[i]];
        else if (w[to[i]]>max2) max2=w[to[i]];
    }
    if (max1*max2>ans.MAX_val)
        ans.MAX_val=max1*max2;
    ans.sum=(ans.sum+val*val-power)%mod;
    
    return ans;
}

int main(){
    int n;
    cin>>n;
    for (int i=1,u,v;i<n;i++){
        cin>>u>>v;
        build(u,v);
        build(v,u);
    }
    for (int i=1;i<=n;i++) cin>>w[i];
    
    node x=dfs(1,0,0);
    cout<<x.MAX_val<<" "<<x.sum<<endl;
    return 0;
}