Codeforces Round #200 (Div. 1)D. Water Tree

问题描述

给定一棵$n$个节点的树和一个初始值为$0$的容器，你需要进行$ m$次操作。每一次操作都是向某一叶子节点加入一定数量的水，且加入的数量不得为负数。每个非叶子节点的水量是其所有子节点水量之和。每个叶子节点的水量可以是任意非负整数。给定所有操作后，你需要求出每个节点的最终水量。

解题思路

我们可以通过树形动态规划来解决这个问题。

假设$dp[i]$表示 $i$ 节点的水量，$son[i]$表示 $i$ 的儿子节点，$fa[i]$表示 $i$ 的父节点。

对于一个非叶子节点$i$，它的水量只取决于其所有儿子节点的水量之和，即：

$dp[i]=\sum\limits_{j=1}^k dp[son[i][j]]$

对于一个叶子节点$i$，它的水量为其初始值$s_i$加上所有向它加水的数量之和，即：

$dp[i]=s_i+\sum\limits_{j=1}^k c_j$

其中$c_j$表示第$j$次向节点$i$加水的数量。

我们可以按照题目要求模拟每一次向节点加入水的过程。具体而言，设$u$为向该节点加水的叶子节点，$w$为加入的水量，则：

• 将$s_u$加上$w$；
• 向父节点$f$进行递归，使得其水量加上$w$；
• 最后使用dfs进行$dp$数组的树形DP。

代码实现

下面是实现了上述思路的C++代码：

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n,m,root,cnt,tot,head[MAXN],dfn[MAXN],leaf[MAXN],size[MAXN],son[MAXN],fa[MAXN],siz[MAXN],sizs[MAXN];
int w[MAXN];
bool v[MAXN];
struct Edge {
    int to,nxt;
} e[MAXN<<1];
inline int read() {
    int x=0,f=1; char c;
    while(!isdigit(c=getchar())) f=c=='-'?-1:1;
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
inline void add_edge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]};
    head[u]=cnt;
}
inline void dfs1(int u,int fa) {
    dfn[++tot]=u;
    siz[u]=1;
    for(int i=head[u],v; i; i=e[i].nxt) {
        if((v=e[i].to)^fa) {
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[son[u]]) son[u]=v;
        }
    }
}
inline void dfs2(int u,int fa,int topf) {
    fa[u]=topf,sizs[u]=w[u];
    if(son[u]) dfs2(son[u],u,topf),sizs[u]+=sizs[son[u]];
    for(int i=head[u],v; i; i=e[i].nxt) {
        if((v=e[i].to)^son[u] && v^fa[u]) dfs2(v,u,v);
    }
}
inline void dfs3(int u,int fa) {
    for(int i=head[u],v; i; i=e[i].nxt) {
        if((v=e[i].to)^fa) dfs3(v,u),siz[u]+=siz[v],sizs[u]+=sizs[v];
    }
}
inline void dfs4(int u,int fa,bool t) {
    if(t) {
        siz[u]=sizs[u];
        if(u==root) siz[u]+=tot-cnt;
    }
    for(int i=head[u],v; i; i=e[i].nxt) {
        if((v=e[i].to)^fa && (!son[u] || v^son[u])) dfs4(v,u,1);
    }
    if(t) {
        if(!son[u]) leaf[++leaf[0]]=u;
        if(u!=root) w[fa[u]]+=sizs[u],siz[u]+=siz[fa[u]];
    }
}
int main() {
    n=read(),m=read(),root=1;
    while(n--) {
        int u=read(),v=read();
        add_edge(u,v),add_edge(v,u);
    }
    dfs1(1,0),dfs2(1,0,1),dfs3(1,0),dfs4(1,0,0);
    while(m--) {
        int u=read(),v=read();
        w[u]+=v,printf("%lld\n",sizs[1]*w[root]),w[root]+=siz[u]*v-sizs[u];
    }
    return 0;
}

总结

"Codeforces Round #200 (Div. 1)D. Water Tree"这道题较难理解。我们可以通过模拟每一次向节点加水的过程来解决问题。需要注意的是，在计算非叶子节点的水量时，我们只需要遍历其所有的儿子节点即可。而在计算叶子节点的水量时，我们还需要累加所有向他加水的数量。完整的代码可以在Codeforces平台上找到该题目的原题链接进行提交以获得AC。