Vijos1906 联合权值 NOIP2014Day1T2 树形动态规划

时间:2021-10-08 11:46:32

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解


题目传送门 - Vijos1906


题意概括

  有一棵树,每一个节点都有一个权值w[i]。下面说的x,y都是该树中的节点。

  对于点对(x,y),x,y,保证x和y距离为2,那么他们就可以联合,会产生w[x]*w[y]的联合权值。

  注意:点对(x,y)和(y,x)是不同的。

  现在要回答两个问题:

  1. 所有可以联合的点对的最大联合权值。

  2. 对于所有不同的点对(x,y),求联合权值和,答案对10007取模。


题解

  在一棵树上?

  首先看完体面,觉得像一道树形dp题。

  其实就是一道树形dp题。

  

  我们按照dfs的顺序,首先,我们考虑较简单的一部分。

  对于询问2,我可以先计算一半(点对的逆序也算不同)。

  对于节点x,我们分成两种大情况考虑:

  1. 它与它的儿子的儿子的联合权值。

  2. 它的儿子和它的儿子的联合权值。

  首先考虑第一种。

  做法:

    对于每一个节点,设置两个数组:sum[i]和Max[i],分别表示其子节点的权值和与最大权值。

    这两个量是非常好维护的。

    那么如何统计?

    对于每一个节点,把它和它的儿子的儿子联合即可 —— 两次联合,分别对应两种询问,一次与儿子的sum结合,一次与儿子的Max结合。

  然后第二种:

    对于sum,其实很简单,对于当前累加的部分sum[rt](rt为当前节点),直接联合累加即可。

    不解释,自己看代码。

    那么max也差不多。

代码

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;
const int N=+,M=N*,mod=;
vector <int> son[N];
int n,w[N],sum[N],Max[N],ansMax,anssum;
void dfs(int prev,int rt){
sum[rt]=Max[rt]=;
for (int i=;i<son[rt].size();i++)
if (son[rt][i]!=prev){
int v=son[rt][i];
dfs(rt,v);
anssum=(anssum+w[rt]*sum[v])%mod;
ansMax=max(ansMax,w[rt]*Max[v]);
anssum=(anssum+sum[rt]*w[v])%mod;
ansMax=max(ansMax,w[v]*Max[rt]);
sum[rt]=(sum[rt]+w[v])%mod;
Max[rt]=max(Max[rt],w[v]);
}
}
int main(){
scanf("%d",&n);
for (int i=;i<=n;i++)
son[i].clear();
for (int i=,a,b;i<n;i++){
scanf("%d%d",&a,&b);
son[a].push_back(b);
son[b].push_back(a);
}
for (int i=;i<=n;i++)
scanf("%d",&w[i]);
ansMax=anssum=;
dfs(,);
printf("%d %d",ansMax,anssum*%mod);
return ;
}