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;
}