首页 > 代码库 > Codeforces 765E. Tree Folding [dfs][树形dp]

Codeforces 765E. Tree Folding [dfs][树形dp]

2024-09-04 14:02:11   218人阅读

题解：
先从节点1开始dfs。
对于每一个节点，用一个set记录：以该点为根的子树的深度。

a) 如果此节点的某个子节点打出了GG,则此节点直接打出GG。

b) 若set的元素个数<=1,那么，以该点为根的子树，显然是可以
缩成一条链滴！且该点为链的端点。
c) 若set元素个数=2，以该点为根的子树，也可以收缩成一条链，
且该点不是链的端点。此时，我们继续分类讨论。
　　i） 该点没有父亲。我们成功找到了一条链~岂不美哉。
　　ii) 该点有父亲，那么在链上会长出一根奇怪的东西。那我们赶紧报警，把该点赋给root，并打出GG
d)若set中元素个数>2,直接打出GG！

如果从1开始dfs求索未得，那一定是root的打开方式不对。我萌以root为起点再来一遍dfs。
如果还不行，那就真.GG。

#include <iostream>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;
const int NICO = 200000 + 10;
vector<int> vec[NICO];
int n, u, v, root;
int dfs(int x, int par)
{
    set<int> st;
    for(int i=0;i<vec[x].size();i++)
    {
        int cur = vec[x][i];
        if(cur == par) continue;
        int t=dfs(cur, x);
        if(t == -1) return -1;// 子节点都已经报警了，就不要再dfs啦！
        st.insert(t+1);
    }
    if(st.size() == 0) return 0;
    if(st.size() == 1) return *st.begin();
    if(st.size() == 2 && par == 0) return *st.rbegin() + *st.begin();
    root = x;                 // 风起于青萍之末~ 此刻，报警吧！
    return -1;
}
int main()
{
    cin >> n;
    for(int i=1;i<n;i++)
    {
        cin >> u >> v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    int ans = dfs(1, 0);
    if(ans == -1 && root) ans = dfs(root, 0);
    while(ans%2==0)
    {
        ans /= 2;
    }
    cout << ans << endl;
}

 

　　

 

Codeforces 765E. Tree Folding [dfs][树形dp]


联系
我们