题解：P11967 [GESP202503 八级] 割裂

· · 题解

题意

给定一颗树，几对好点 \{\langle u_1, v_1 \rangle, \langle u_2, v_2 \rangle, \dots, \langle u_a, v_a \rangle\} 和一个坏点对 \langle b_u, b_v \rangle。\langle u_i, v_i \rangle 之间的点不能，只能选 \langle b_u, b_v \rangle 之间的点，求有几个点可以被选择。

思路

以 b_u 为根，则只能选从 b_v 到根上的路径，用一个 bool 数组记录（不妨在 b_u 到 b_v 的路径上的为 true）。

定义 f_i 表示共有多少组 \langle u_i, v_i \rangle 的路径经过点 i。

对于每一组 \langle u_i, v_i \rangle，树上差分即可。

具体来说，就是：

  f[u[i]]++;
  f[v[i]]++;
  f[LCA(u[i],v[i])]--;
  f[father[LCA(u[i],v[i])]]--;

然后对于每一组父子关系 (fa,x)，f[fa]+=f[x] 即可。

点 p 不在任意一组 \langle u_i, v_i \rangle 所在路径上，当且仅当 f_p=0。

综上所述，一个点 i 可以被选择，当且仅当 ans_i = true 并且 f_i=0。

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Beginning;

#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using PII=pair<int,int>;
using PIB=pair<int,bool>;
using PBI=pair<bool,int>;
using PBB=pair<bool,bool>;
using PDI=pair<double,int>;
using PID=pair<int,double>;

namespace Memory_Love{
    int read(){ int x=0; bool flag=1; char ch=getchar();
        while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
        while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return flag? x:-x;}
    template<typename T> void read(T &x){ bool flag=1; x=0; char ch=getchar();
        while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
        while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} x=(flag? x:-x);}
    template<typename T,typename ...Args> void read(T &Re,Args &...Res){read(Re),read(Res...);}
    template<typename T> void write(T x,char ch=0){if(x<0) x=-x,putchar('-');
        static short s[35],top=-1; do{s[++top]=x%10;x/=10;}while(x);
        while(~top) putchar(s[top--]+48); if(ch) putchar(ch);}
    int gcd(int a,int b){return b==0? a:gcd(b,a%b);}
    int lcm(int a,int b){return a/gcd(a,b)*b;}
    int lowbit(int x){return (x&-x);}
} using namespace Memory_Love;
const int N=1e6+5;
int n,m,s,t;

namespace Graph
{
    int head[N],tot;
    struct edge
    {
        int v,next;
    }e[N<<1];
    void G_init()
    {
        memset(head,-1,sizeof(head));
        tot=-1;
    }
    void add(int u,int v)
    {
        e[++tot]=(edge){v,head[u]};
        head[u]=tot;
    }
    void add_edge(int u,int v)
    {
        add(u,v),add(v,u);
    }
} using namespace Graph;

vector<PII> G;

namespace SP
{
    int dfn[N],rev[N],cnt;
    int depth[N],father[N];
    int son[N],top[N],SIZE[N];
    void dfs1(int x,int fa)
    {
        int i;
        SIZE[x]=1;
        father[x]=fa;
        depth[x]=depth[fa]+1;
        for(i=head[x];~i;i=e[i].next)
        {
            int y=e[i].v;
            if(y==fa)
            continue;
            dfs1(y,x);
            SIZE[x]+=SIZE[y];
            if(SIZE[y]>SIZE[son[x]])
            son[x]=y;
        }
    }
    void dfs2(int x,int topx)
    {
        int i;
        dfn[x]=++cnt;
        rev[cnt]=x;
        top[x]=topx;
        if(son[x]) dfs2(son[x],topx);
        for(i=head[x];~i;i=e[i].next)
        {
            int y=e[i].v;
            if(!top[y])
            dfs2(y,y);
        }
    }
    void init(int root)
    {
        dfs1(root,0);
        dfs2(root,root);
    }
    int LCA(int x,int y)
    {
        while(top[x]!=top[y])
        {
            if(depth[top[x]]<depth[top[y]])
            swap(x,y);
            x=father[top[x]];
        }
        return (depth[x]<depth[y]? x:y);
    }
}

int f[N];
bool ans[N];
void dfs(int x,int fa)
{
    int i;
    if(x==t) ans[x]=1;
    for(i=head[x];~i;i=e[i].next)
    {
        int y=e[i].v;
        if(y==fa)
        continue;
        dfs(y,x);
        ans[x]|=ans[y];
        f[x]+=f[y];
    }
}

bool Ending;
signed main()
{
    int i,u,v,Ans=0;
    read(n,m);
    G_init();
    for(i=1;i<=n-1;i++)
    {
        read(u,v);
        add_edge(u,v);
    }
    for(i=1;i<=m;i++)
    {
        read(u,v);
        G.push_back(mp(min(u,v),max(u,v)));
    }
    read(s,t);
    SP::init(s);

    for(auto t:G)
    {
        int lca=SP::LCA(t.fi,t.se);
        f[t.fi]++,f[t.se]++;
        f[lca]--,f[SP::father[lca]]--;
    }
    dfs(s,0);
    for(i=1;i<=n;i++)
    {
        if(ans[i] && f[i]==0)
        Ans++;
    }
    write(Ans,'\n');

    cerr<<"\nused:"<<(abs(&Ending-&Beginning)/1048576)<<"MB\n";
    return 0;
}