题解 P8456 「SWTR-8」地地铁铁

tzc_wk · 2023-04-19 15:45:11 · 题解

挺有意思的结论题，结论的证明比较复杂。据出题人说他大概想了几天几夜才证出来，所以本篇题解并不详细给出结论证明，如果有兴趣可以自己去看出题人的题解：https://www.luogu.com.cn/blog/AlexWei/solution-p8456。

首先涉及到简单路径，肯定往双连通分量的方向思考。因此我们首先建出圆方树，并将所有可能的点对分为在同一个点双内和不在同一个点双内的情况处理：

• 先考虑在同一个点双内的情况，显然如果点双里所有边颜色都相同就似了，这种情况下点双内任意一对点对间都不存在经过两种颜色边的路径。如果两种颜色都有，你的第一反应肯定感觉是任意点对间都存在符合条件的路径，但稍微想想就可以找出反例：长度为 3 的环，两个 D 一个 d，这样 D 和 d 分界处两个点之间不存在符合要求的路径。思考这样的情况出现的原因：点双里总共只有两个点同时存在 D 与 d 的出边，这样你要么一直待在 d 的区域，要么一直待在 D 的区域，如果要从一个区域切换到另一个区域就必须经过这两个点，这样就违背了简单路径。那么是否只有这一个反例呢？答案是肯定的，也就是说如果一个点双里有且只有两个点满足其既有 D 也有 d 的出边，那么其对答案的贡献就是 \dbinom{siz}{2}-1，否则贡献 \dbinom{siz}{2}。比较感性的理解方式是你可以走到另一个存在两种颜色出边的点在那里切换颜色。
• 再考虑不在同一个点双内的情况。称所有边都是 D 的点双为黑点双，所有边都是 d 的点双为白点双，既存在 D 又存在 d 的点双为混色点双，那么结论是如果两点在圆方树上的路径上全是黑点双，或者全是白点双的时候才不合法。因为如果既存在黑点双又存在白点双，那么显然是合法的，否则其至少存在一个混色点双，根据上一部分的结论，对于一个混色点双而言，最坏的情况就是上文所说的不合法的点对，这种情况下两点之间存在只由 D 组成的路径，也存在只由 d 组成的路径，但是不存在包含 D 和 d 的路径，但是由于我们经过了至少一个点双，也就是我们可以通过其他部分的包含 D 还是包含 d，来决定这两点之间我们是选择只包含 D 的路径，还是只包含 d 的路径，这样上述点对必然合法，直接并查集求即可。

const int MAXN=5e6;
int n,m,hd[MAXN+5],to[MAXN+5],nxt[MAXN+5],val[MAXN+5],ec=1;
vector<int>g[MAXN+5];int typ[MAXN+5];ll res;
void adde(int u,int v,int w){
    to[++ec]=v;val[ec]=w;nxt[ec]=hd[u];hd[u]=ec;
    to[++ec]=u;val[ec]=w;nxt[ec]=hd[v];hd[v]=ec;
}
int dfn[MAXN+5],low[MAXN+5],tim=0,stk[MAXN+5],tp=0;
int e_stk[MAXN+5],e_top,ncnt,in[MAXN+5];
void tarjan(int x){
    dfn[x]=low[x]=++tim;stk[++tp]=x;
    for(int e=hd[x];e;e=nxt[e]){
        int y=to[e];
        if(!dfn[y]){
            e_stk[++e_top]=e>>1;in[e>>1]=1;
            tarjan(y);chkmin(low[x],low[y]);
            if(low[y]>=dfn[x]){
                vector<int>V,E;
                int o;++ncnt;
                do{o=stk[tp--];V.pb(o);}while(o^y);V.pb(x);
                do{o=e_stk[e_top--];in[o]=0;E.pb(o);}while(o^(e>>1));
                static int msk[MAXN+5];
                for(int z:V)g[ncnt].pb(z),g[z].pb(ncnt),msk[z]=0;
                int totmsk=0,sum=0;
                for(int z:E){
                    totmsk|=(1<<val[z<<1]);
                    msk[to[z<<1]]|=(1<<val[z<<1]);
                    msk[to[z<<1|1]]|=(1<<val[z<<1]);
                }
                typ[ncnt]=totmsk-1;
                for(int z:V)sum+=(msk[z]==3);
                if(sum==2)res--;
            }
        }else{
            chkmin(low[x],dfn[y]);
            if(dfn[y]<dfn[x]&&!in[e>>1])e_stk[++e_top]=e>>1;
        }
    }
}
int f[MAXN+5],siz[MAXN+5];
int find(int x){return (!f[x])?x:f[x]=find(f[x]);}
void merge(int x,int y){x=find(x);y=find(y);f[x]=y;siz[y]+=siz[x];}
int main(){
    scanf("%*d%d%d",&n,&m);res=1ll*n*(n-1)/2;
    for(int i=1,u,v;i<=m;i++){
        static char buf[6];scanf("%d%d%s",&u,&v,buf+1);
        adde(u,v,buf[1]=='D');adde(v,u,buf[1]=='D');
    }ncnt=n;tarjan(1);
    for(int i=1;i<=n;i++)siz[i]=1;
    for(int i=n+1;i<=ncnt;i++)if(typ[i]==0)for(int y:g[i])merge(i,y);
    for(int i=1;i<=ncnt;i++)if(find(i)==i)res-=1ll*siz[i]*(siz[i]-1)/2;
    memset(f,0,sizeof(f));memset(siz,0,sizeof(siz));
    for(int i=1;i<=n;i++)siz[i]=1;
    for(int i=n+1;i<=ncnt;i++)if(typ[i]==1)for(int y:g[i])merge(i,y);
    for(int i=1;i<=ncnt;i++)if(find(i)==i)res-=1ll*siz[i]*(siz[i]-1)/2;
    printf("%lld\n",res);
    return 0;
}