Codeforces Round 875 (Div. 2) C. Copil Copac Draws Trees( DFS )

发布时间 2023-10-21 13:13:20作者: ikunhuaji

Codeforces Round 875 (Div. 2) C. Copil Copac Draws Trees

思路:

在输入树的边的同时记录他们的输入顺序

从 1 开始跑 DFS ,遇到未连上的边时 , 有两种情况(用 q 表示当前点的顺序序号)

1.边的顺序在这个点连上之前,那么 DFS 的 deep 应 +1 , 即这条边应在 deep+1 次时连上

2.边的顺序在这个点连上之后,那么 DFS 的deep不变 , 即这条边在 deep 次连上

对于 deep 取 max 即可

#define int long long
#define ld long double

using namespace std;

const int N = 2e5 + 10;

int t,n;
vector<pair<int, int>>h[N];
bool st[N];
int ans;

void dfs(int u, int q, int deep)
{
    for (auto it : h[u])
    {
        int v = it.first, p = it.second;

        if (st[v])
        {
            continue;
        }

        st[v] = true;

        if (p < q)
        {
            ans = max(ans, deep + 1);
            dfs(v, p, deep + 1);
        }
        else
        {
            ans = max(ans, deep);
            dfs(v, p, deep);
        }
    }
}

void solve()
{
    cin >> n;

    st[1] = true;
    for (int i = 1; i <= n; i++)
    {
        h[i].clear();
        st[i] = false;
    }

    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;

        h[a].push_back({ b,i });
        h[b].push_back({ a,i });
    }

    ans = 0;
    dfs(1, 0, 1);
    cout << ans << endl;
}

signed main()
{
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}