题解：CF1970C3 Game on Tree (Hard)

asckertui · 2026-11-13 20:03:49 · 题解

蒟蒻的第一篇 CF 题解。

没做过前置题目的做一下：medium。

看到数据范围，显然换根 dp。

考虑用 ans 数组把每一个节点为根的答案存下来，然后 O(1) 回答。

第一遍 dfs 和 medium 版本一样，定义 dp1_u 为以 u 为根的子树必胜或必败。

转移就是如果有一个儿子 v 满足 dp1_v=0，那么直接选择这个分支，把必败留给对面，那么必胜。

重点来看到第二遍 dfs。

由于第一遍 dfs 只考虑了往儿子方向，所以第二遍的 dp_u 定义为 u 往父亲方向转移的必胜或必败。

注意其实就是先往父亲走一步，然后再统计。

考虑计算 dp_v。

因为第一步只能向上走到 u，所以如果 dp_u=1，那么必败。

假设已经走到了 u，那么只能走到 u 的其它儿子。统计 u 的儿子中必败的数量，记为 cnt。

分类讨论：如果 dp1_v=1，说明 v 不在 cnt 里，那么只要 cnt>0 即可。

理解一下，先走到 u，然后交给对手，他选择走到我方必败的那个儿子，我方就输了。

如果 dp1_v=0，说明 v 在 cnt 里，那么要 cnt>1。

这下我们就推完了 dp 和 dp1 数组，接下来考虑统计 ans_u。

儿子方向，只需要 cnt>0 即可把必败态让给对手，必胜；

父亲方向，需要有父亲且 dp_u=1 即可。

那么答案就统计完了。循环 t 输出即可。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,t,s,dp1[200005],dp[200005],ans[200005];
vector<int> g[200005];
void dfs1(int u,int f)
{
    for(int v:g[u])
    {
        if(v==f)
        {
            continue;
        }
        dfs1(v,u);
        if(dp1[v]==0)
        {
            dp1[u]=1;
        }
    }
}
void dfs2(int u,int f)
{
    int cnt=0;
    for(int v:g[u])
    {
        if(v==f)
        {
            continue;
        }
        cnt+=!dp1[v];
    }
    ans[u]=f!=0&&dp[u]||cnt>0;
    for(int v:g[u])
    {
        if(v==f)
        {
            continue;
        }
        if(dp[u]||cnt>1||dp1[v]&&cnt==1)
        {
            dp[v]=0;
        }
        else
        {
            dp[v]=1;
        }
        dfs2(v,u);
    }
}
int main()
{
    cin>>n>>t;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=t;i++)
    {
        cin>>s;
        if(ans[s])
        {
            cout<<"Ron\n";
        }
        else
        {
            cout<<"Hermione\n";
        }
    }
    return 0;
}

如果各位觉得讲的不对，欢迎指正。