CF1276B Two Fairs

扫码查看

Link

Solution

把圆方树建出来,然后就显然了。直接将a,b两侧的子树内节点数相乘即可。

考虑两种情况:

  • a,b没有祖孙关系。这一种ans就是\((siz[a]-1)\times (siz[b]-1)\)
  • a,b有祖孙关系。不失一般性地假设a是b的祖先。这是a一侧的子树不再是\(siz[a]-1\),应该是a子树以外的部分。设b往上走一直走到a儿子处的方点为s,ans就是\((n-siz[s]-1)*(siz[b]-1)\)。注意是a往下的第一个方点而不是圆点,这是我一开始没考虑清楚的地方。方点代表的点双上,不是a的点,都可以不经过a就到达b侧子树内。他们是不应计算进答案的。

tips: \(siz[]\)指的是子树内圆点个数。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){//be careful for long long!
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x;
}

const int N=2e5+10,M=5e5+10;
int n,m,a,b,stk[N],tp,cnt,dfn[N],low[N],dfc,siz[N<<1],vis[N<<1],fa[N<<1];
vector<int> r_E[N],E[N<<1];
#define pb(x) push_back(x)

inline void Tarjan(int nw,int pa=0){
    dfn[nw]=low[nw]=++dfc;stk[++tp]=nw;
    for(int to:r_E[nw])
    if(to^pa){
        if(!dfn[to]){
        Tarjan(to);
        low[nw]=min(low[nw],low[to]);
        if(dfn[nw]<=low[to]){
            ++cnt;
            for(int x=0;x^to;--tp){
            x=stk[tp];
            E[cnt].pb(x),E[x].pb(cnt);
            }
            E[cnt].pb(nw),E[nw].pb(cnt);
        }
        }
        else low[nw]=min(low[nw],dfn[to]);
    }
}

inline void Dfs(int nw,int pa,int type){
    vis[nw]=type;siz[nw]=(nw<=n);fa[nw]=pa;
    if(nw==a)type=1;else if(nw==b)type=2;
    for(int to:E[nw])
    if(to^pa){
        Dfs(to,nw,type);
        siz[nw]+=siz[to];
    }
}

int main(){
    int T=read();
    for(int t=1;t<=T;++t){
    cnt=n=read(),m=read();a=read(),b=read();
    for(int i=1;i<=n;++i)r_E[i].clear();
    for(int i=1,tim=(n<<1);i<=tim;++i)E[i].clear();
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        r_E[u].pb(v),r_E[v].pb(u);
    }
    memset(dfn,0,sizeof(int)*(n+1));
    dfc=tp=0;Tarjan(1);
    Dfs(1,0,0);
    if(vis[a]==2){
        int s=a;while(fa[s]!=b)s=fa[s];
        printf("%lld\n",1ll*(siz[a]-1)*(n-siz[s]-1));
    }
    else if(vis[b]==1){
        int s=b;while(fa[s]!=a)s=fa[s];
        printf("%lld\n",1ll*(siz[b]-1)*(n-siz[s]-1));
    }
    else printf("%lld\n",1ll*(siz[a]-1)*(siz[b]-1));
    }
    return 0;
}
12-13 19:46
查看更多