CF1689C Infected Tree 题解

· · 题解

这是个动态规划啊……

还是一个比较基础的树形动规。

当然赛时我差点写了一个树链剖分，然后突然发现是一棵二叉树……

可惜同机房的 @artalter 大佬和 @Sakura_Lu 大佬没有注意惨遭爆零。

言归正传，我们当然想尽可能多的保留节点，而且每一次肯定是删除被病毒感染的节点的某个子节点。

而删除之后我们的问题就可以转化为它的另一个儿子（注意为二叉树）的根被感染病毒能保留多少节点的子问题，

那么很明显可以考虑一下动规。

它的状态也很简单：dp[i] 表示在以 i 为根的子树中，若 i 被感染病毒，最多能保留多少节点。

那么考虑如何转移，很明显我们考虑删掉 i 的哪一个子节点即可。

我们就首先来分别考虑究竟删除哪一个子节点。

假设删除 lson，那么相当于在 lson 的子树里我们可以保留下 size[lson]-1 个节点，size[i] 代表以 i 为根的子树的大小（包含节点 i），

而在 rson 的子树里，我们依旧可以保留下 dp[rson] 个节点，所以最终的状态转移方程就是：

dp[i]=\operatorname{max}(dp[lson]+size[rson]-1,dp[rson]+size[lson]-1)

需要注意可能子树为空，那么 size[son]-1 就是一个负数，所以需要对 0 取 \operatorname{max}。

为避免这种情况，我们要先进行 dfs 再更新 size 和 dp 数组。

以及多组数据所以每次需要将各种数组清零，清零 head 数组也相当于清零边，小小地卡一点常数。

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=1e9+7;
struct Edge{
    int pre,to;
}edge[WR];
int t;
int n,sze[WR];
int head[WR],tot;
int dp[WR];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
void add(int u,int v){
    edge[++tot].pre=head[u];
    edge[tot].to=v;
    head[u]=tot;
}
void dfs(int u,int root){
    sze[u]=1,dp[u]=0;//dp数组存储如果我被感染了能活多少个
    int sum=0;
    for(int i=head[u];i;i=edge[i].pre){
        int v=edge[i].to;
        if(v!=root){
            dfs(v,u);
            sum+=dp[v];
            sze[u]+=sze[v];
        }
    }
    for(int i=head[u];i;i=edge[i].pre){
        int v=edge[i].to;
        if(v!=root){
            dp[u]=max(dp[u],sum-dp[v]+sze[v]-1);
        }
    }
}
signed main(){
    t=read();
    while(t--){
        n=read();
        tot=0;
        for(int i=1;i<=n;i++) head[i]=0;
        for(int i=1;i<n;i++){
            int u=read(),v=read();
            add(u,v);
            add(v,u);
        }
        dfs(1,0);
        printf("%lld\n",dp[1]);
    }
    return 0;
}