【题解】CF1830A Copil Copac Draws Trees

你考虑对于每一条边打上时间标记，然后在树上 DFS 的时候维护一下以 \(u\) 为根的答案即可，然后将答案合并，反正很简单，看代码就懂。

code:

#include<bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 8;
int t,n;
struct Edge{
	int to,next,val;
}edge[NN << 1];
int head[NN],cnt;
void init(){
	for(int i = 1; i <= n; ++i) head[i] = -1;
	cnt = 1;
}
void add_edge(int u,int v,int w){
	edge[++cnt] = {v,head[u],w};
	head[u] = cnt;
}
int dfs(int u,int fa,int pre){
	int ans = 0;
	for(int i = head[u]; i != -1; i = edge[i].next){
		int v = edge[i].to,val = edge[i].val;
		if(v == fa) continue;
		ans = max(ans,dfs(v,u,val) + (val < pre));
	}
	return ans;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);init();
		for(int i = 1,u,v; i < n; ++i) scanf("%d%d",&u,&v),add_edge(u,v,i),add_edge(v,u,i);
		printf("%d\n",dfs(1,1,0)+1);
	}
}