题解：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。

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