AHOI 2022 T4

ix35 · 2022-05-10 17:20:53 · 题解

看上去比 std 做法快很多而且好写很多？

首先，我们做一些准备工作，如果研究 (s_i,t_i) 覆盖了研究 (s_j,t_j)，那么我们就删掉 (s_j,t_j)，这可以排序后用一个 DFS 序上的树状数组做到 O(n\log n)。于是，现在认为研究之间两两没有包含关系。

接下来我们考虑所有满足以下条件的 (s_i,t_i)：不存在某个 t_j 是其后代。这样的 t_i 实际上就是一组极大的两两没有祖先关系的 t_i。我们称这些研究 (s_i,t_i) 是关键的。

对于根结点 1 的每个儿子 x_1,\ldots,x_k，考虑其中关键研究的个数，不妨设为 z_1\leq \ldots\leq z_k，那么我们首先给出一个答案的下界，那就是 \lceil(\sum z_i)/2\rceil，因为任意三个关键研究不可能被一条路径覆盖（容易证明），所以一条路径至多只能满足两个研究。

当 z_1+\ldots+z_{k-1}\ge z_k 时，这个下界是可以取到的，因为我们只需将关键研究两两配对，使得同一对中的关键研究属于 1 的不同子树，然后用一条 LCA 为 1 的路径将它们覆盖。

而当 z_1+\ldots+z_{k-1}<z_k 时就不一定可行了，因为这时没有上述配对方案。但我们知道此时 y_1,\ldots,y_{k-1} 子树中的关键研究是不会出现配对的（总是可以调整成与 y_k 子树中的关键研究配对），所以我们可以递归儿子 y_k，将答案加上 z_1+\ldots+z_{k-1}，之后我们就有了 z_1+\ldots+z_{k-1} 条“闲置路径”，可以免费覆盖任意一个关键研究。

事实上，上面的过程类似于在寻找所有关键研究中的 t_i 的重心。

上面的算法有一些需要修补的地方，从 1 递归到 y_k 时我们可能漏掉了一些 s_i=1 的非关键研究，之后可能会覆盖不到，下面来解决这个问题。

我们发现，从 1 递归到 y_k 时我们加的限制其实是：添加了一些“免费”的路径，其中一部分是可以连向 y_k 的任意后代的，另一部分则只能连向特定的某个结点的任意后代。

于是，我们引入一个对结点的标记，一个结点上有标记就表示：存在一条免费的路径可以连到这个结点的任意后代。

每一轮递归流程如下：

• 首先计算 z_1,\ldots,z_k，如果 z_1+\ldots+z_{k-1}<z_k，那么先令 免费路径数 增加 z_1+\ldots+z_{k-1}，同时答案也增加 z_1+\ldots+z_{k-1}；

• 接下来考虑所有 s_i=1 的研究 (s_i,t_i)：

  1. 如果存在 t_i 的一个比当前点更深的祖先拥有标记，则找到其中最深的标记，将其移动到 t_i 上；
  2. 如果不存在上述拥有标记的祖先，则 如果当前免费路径数不为 0，则令免费路径数 -1，同时在 t_i 上打标记；
  3. 如果不存在上述拥有标记的祖先，而且免费路径数为 0，则答案 +1，同时在 t_i 上打标记。

标记以及 z_i 的求解都可以用树状数组实现，复杂度为 O((n+m)\log n)。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010;
struct P {int a,b;} p[MAXN];
int t,n,m,x,y,tot,ans,bt[MAXN],tb[MAXN],sy[MAXN],f[MAXN];
int dfn[MAXN],ed[MAXN],vis[MAXN],dep[MAXN];
vector <int> v[MAXN],w[MAXN];
void modify1 (int x,int v) {
    for (int i=x;i<=n;i+=(i&(-i))) {bt[i]+=v;}
}
int query1 (int x) {
    int res=0;
    for (int i=x;i;i-=(i&(-i))) {res+=bt[i];}
    return res;
}
void modify2 (int x,int v) {
    for (int i=x;i<=n;i+=(i&(-i))) {tb[i]+=v;}
}
int query2 (int x) {
    int res=0;
    for (int i=x;i;i-=(i&(-i))) {res+=tb[i];}
    return res;
}
bool cmp (P a,P b) {return dep[a.a]==dep[b.a]?dep[a.b]>dep[b.b]:dep[a.a]<dep[b.a];}
void dfs (int x,int fa) {
    dfn[x]=ed[x]=++tot,dep[x]=dep[fa]+1,f[x]=fa;
    int len=v[x].size();
    for (int i=0;i<len;i++) {
        if (v[x][i]==fa) {continue;}
        dfs(v[x][i],x);
        ed[x]=ed[v[x][i]];
    }
    return;
}
void dfs2 (int x,int fa) {
    int len=v[x].size(),flg=(vis[x]==1);
    for (int i=0;i<len;i++) {
        if (v[x][i]==fa) {continue;}
        dfs2(v[x][i],x);
        vis[x]+=vis[v[x][i]];
    }
    if (vis[x]==1&&flg) {modify1(dfn[x],1);}
    return;
}
int main () {
    scanf("%d",&t);
    for (int ii=1;ii<=t;ii++) {
        scanf("%d%d",&n,&m);
        tot=ans=0;
        for (int i=1;i<=n;i++) {v[i].clear(),w[i].clear(),bt[i]=tb[i]=sy[i]=vis[i]=0;}
        for (int i=1;i<=n-1;i++) {
            scanf("%d%d",&x,&y);
            v[x].push_back(y),v[y].push_back(x);
        }
        dfs(1,0);
        for (int i=1;i<=m;i++) {
            scanf("%d%d",&x,&y);
            p[i].a=x,p[i].b=y;
        }
        sort(p+1,p+m+1,cmp);
        for (int i=1;i<=m;i++) {
            int sum=query2(ed[p[i].b])-query2(dfn[p[i].b]-1);
            if (sum==0) {w[p[i].a].push_back(p[i].b),vis[p[i].b]=1;}
            modify2(dfn[p[i].b],1);
        }
        for (int i=1;i<=n;i++) {tb[i]=0;}
        dfs2(1,0);
        int cur=1;
        while (cur) {
            int len=v[cur].size(),sum=0,mx=0,alp=0;
            for (int i=0;i<len;i++) {
                if (v[cur][i]==f[cur]) {continue;}
                int tmp=query1(ed[v[cur][i]])-query1(dfn[v[cur][i]]-1);
                if (tmp>mx) {mx=tmp,alp=v[cur][i];}
                sum+=tmp;
            }
            //cout << "    " << cur << "  " << sum << "  " << mx << "  " << sy[cur] << endl;
            if (mx<=sum-mx+sy[cur]) {
                ans+=(sum-sy[cur]+1)/2;
                break;
            }
            sy[cur]+=sum-mx,ans+=sum-mx;
            //cout << cur << "  " << alp << "  " << sy[cur] << "  " << ans << endl;
            int len2=w[cur].size();
            for (int i=0;i<len2;i++) {
                if (dfn[w[cur][i]]<dfn[alp]||ed[alp]<ed[w[cur][i]]) {continue;}
                int val=query2(dfn[w[cur][i]]);
                if (val) {
                    modify2(dfn[val],-val),modify2(ed[val]+1,val);
                    modify1(dfn[val],1),sy[val]--;
                } else if (sy[cur]) {
                    sy[cur]--;
                } else {
                    ans++;
                }
                modify2(dfn[w[cur][i]],w[cur][i]),modify2(ed[w[cur][i]]+1,-w[cur][i]);
                modify1(dfn[w[cur][i]],-1),sy[w[cur][i]]++;
            }
            if (sy[alp]) {
                modify2(dfn[alp],-alp),modify2(ed[alp]+1,alp);
            }
            //cout << cur << "  " << alp << "  " << sy[cur] << "  " << ans << endl;
            sy[alp]+=sy[cur];
            cur=alp;
        }
        printf("%d\n",ans);
    }
    return 0;
}