题解归档 - cf2229E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2229E
• 本地来源：problems/cf2229E/idea.md
• 题目链接：https://codeforces.com/contest/2229/problem/E
• 原始标题：cf2229E

思路

cf2229E

pattern: rooted tree pruning + increasing guard DP.

claim: Root the tree at n. If n is initially a leaf, the only obtainable set is {n}. Otherwise let st be the maximum original non-root leaf. Every later non-root element of S is an increasing "guard" value.

necessary: To move from current guard u to a larger vertex v, all descendants of v must be removable before any value larger than u appears. This is equivalent to mx[v]<u, where mx[v] is the maximum label in the subtree of v excluding v.

sufficient: If mx[v]<u<v, clear all child subtrees of v; no label larger than u can become a leaf first, so v can be made the next guard.

dp: dp[v]=sum dp[u] over mx[v]<u<v, scanned by label with a Fenwick tree. The root n can finish after guard u iff every root-child branch not containing u has maximum label <u.

brute/check: The brute enumerates all legal leaf-removal orders for small n and stores distinct sets.

edge: If deg[n]<=1, n is the maximum leaf from the start, so the answer is 1.

代码

来源：problems/cf2229E/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005,mod=998244353;
vector<ll>ss[maxn+5];
ll deg[maxn+5],f[maxn+5],rt[maxn+5],q[maxn+5],sub[maxn+5],mx[maxn+5],dp[maxn+5],bit[maxn+5];
void add(ll x,ll y,ll n){
    while(x<=n){
        bit[x]=(bit[x]+y)%mod;
        x+=x&-x;
    }
}
ll ask(ll x){
    ll ans=0;
    while(x){
        ans=(ans+bit[x])%mod;
        x-=x&-x;
    }
    return ans;
}
int main(){
    ll t,n,i,j,k,u,v,slsl,st,cur,dq,ans,val,out;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(i=1;i<=n;i++){
            ss[i].clear();
            deg[i]=f[i]=rt[i]=sub[i]=mx[i]=dp[i]=bit[i]=0;
        }
        for(i=1;i<n;i++){
            scanf("%lld%lld",&u,&v);
            ss[u].push_back(v);
            ss[v].push_back(u);
            deg[u]++;
            deg[v]++;
        }
        if(deg[n]<=1){
            printf("1\n");
            continue;
        }
        st=0;
        for(i=1;i<n;i++) if(deg[i]==1) st=i;
        slsl=1;
        q[1]=n;
        f[n]=-1;
        for(i=1;i<=slsl;i++){
            u=q[i];
            for(j=0;j<(ll)ss[u].size();j++){
                v=ss[u][j];
                if(v==f[u]) continue;
                f[v]=u;
                if(u==n) rt[v]=v;
                else rt[v]=rt[u];
                q[++slsl]=v;
            }
        }
        for(i=slsl;i>=1;i--){
            u=q[i];
            sub[u]=u;
            mx[u]=0;
            for(j=0;j<(ll)ss[u].size();j++){
                v=ss[u][j];
                if(f[v]==u){
                    sub[u]=max(sub[u],sub[v]);
                    mx[u]=max(mx[u],sub[v]);
                }
            }
        }
        cur=dq=0;
        for(i=0;i<(ll)ss[n].size();i++){
            v=ss[n][i];
            if(sub[v]>cur){
                dq=cur;
                cur=sub[v];
            }
            else if(sub[v]>dq) dq=sub[v];
        }
        dp[st]=1;
        add(st,1,n);
        for(i=st+1;i<n;i++){
            val=(ask(i-1)-ask(mx[i])+mod)%mod;
            dp[i]=val;
            if(val) add(i,val,n);
        }
        ans=0;
        for(i=st;i<n;i++){
            if(dp[i]==0) continue;
            out=(sub[rt[i]]==cur?dq:cur);
            if(out<i) ans=(ans+dp[i])%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}