题解：CF1830A Copil Copac Draws Trees

树形DP

由于本题的树是一颗有根树，在构建完这颗以

1

为根的树后不难发现：一个点

u

的父边与这个点

u

的父结点

father_u

的父边之间显然存在顺序关系（因为在有根树中，一个点的父节点是唯一确定的）。

具体地说，如果点

u

的父边对应的编号大于点

father_u

的父边编号，则说明这两条边都可以在同一次步骤一中添加。反之则点

u

的父边需要在点

father_u

的父边构建完后执行下一次步骤一时构建。

于是可以对输入的每条边记录按顺序编号，然后对图中的每个点进行 DP。

设

f_i

表示

i

结点的父边是在第几次操作一中构建的。

若

v

的父节点为

u

，

v

的父边编号为

id

，

u

的父边编号为

pre\_id

，此时转移显然：

f_v=f_{u} + [id<pre\_id]

注意初始化

f_1=1

，最后答案即为

\max_{i=1}^n f_i

。

CPP

#define rep(x,y,z) for(int x=y;x<=z;x++)
const int N=2e5+5;
int n;
vector<array<int,2>> E[N];
int f[N];
void dfs(int u,int father,int pre_id){
	for(auto t:E[u]){
		int v=t[0],id=t[1];
		if(v==father) continue;
		f[v]=f[u]+(id<pre_id);
		dfs(v,u,id);
	}
}
void solve(){
	cin>>n;
	rep(i,1,n) E[i].clear();
	rep(i,1,n-1){
		int a,b;
		cin>>a>>b;
		E[a].push_back({b,i});
		E[b].push_back({a,i});
	}
	dfs(1,-1,0);
	int ans=0;
	rep(i,1,n) ans=max(ans,f[i]);
	cout<<ans+1;
}

题解：CF1830A Copil Copac Draws Trees

文章操作

树形DP

相关推荐

评论

题解：CF1830A Copil Copac Draws Trees