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

· · 题解

更好的阅读体验

圆方树入门题。听讲了四次才会做。

假设 D 是 0，d 是 1。先把问题转化为求不合法的方案数，也就是路径只经过一种边权的方案数。

先考虑起点和终点在同一个点双的情况。假设当前点双的大小为 sz。如果这个点双只有一种颜色，那么显然在这个点双内部怎么走都是不合法的路径，方案数为 sz \choose 2。

那么我们考虑如果点双内部含有两种边，那么是否每个点对都合法呢？好像也不是。如图，这个点双内部 (1, 2) 点对也不存在同色路径。

所以经过手玩我们会发现，如果点双内只有两个点同时具有 0 和 1 的出边，那么这两个点之间也不存在两种边权的路径。原因是你要有两种边权的路径，就必须要有边权 0 \to 1 或者 1 \to 0 的切换的地方，但是这两个点之间没有切换的地方；其他点对 (u, v) 一定可以通过 u 走到这个切换的点，然后再由这个点走到 v，来实现路径上有两种颜色。

所以对于一个大小为 sz 的点双，如果是同色的那么不合法路径数量为 sz \choose 2，否则如果只有两个点同时有 01 出边，不合法路径数量为 1，否则为 0。

接下来考虑起终点不在同一个点双的情况，对于这种情况我们在圆方树上分析。

对于一个方点，如果内部只有 0 边我们称之为白点，内部只有 1 边我们称之为黑点，如果两种都有我们称之为灰点。

那么如果一条路径上只有白点或者只有黑点，那就已经寄了，因为不管怎么走都走不到其他颜色的边，因此一定是不合法的路径。

很显然一条路径上同时有白点和黑点的话，一定是合法的。

接下来考虑加入灰点怎么办。如果这个灰点内部有超过 2 个有 01 出边的点，那一定是合法的，因为一定存在一条进入这个方点，在内部行走，再走出这个方点，经过两种颜色边的路径。

那如果有像上图的情况怎么办？假设灰点中，进入点双的点和出点双的点之间有若干条含有两种颜色的路径，但是每条路径只有一种颜色，那么我们可以根据我们方点外我们经过了哪种颜色，在这个灰点中选择另一种颜色，就可以了。

所以，对于起终点在不同点双的情况，答案就是路径上只有白点或只有黑点的路径数量。

所以我们就对白点和黑点分别求一个极大的连通块，假设某个连通块含有的圆点数量为 cnt，那么不合法路径数量就是 cnt \choose 2。

再说一下怎么求一条边属于哪个点双。如果直接枚举出边会被菊花卡成 O(n^2)。

我们在圆方树上随便取一个根，求出每个点的父亲 f_u。

对于原图一条边 (u, v)，要么 u 和 v 是兄弟，要么是祖孙关系。而夹在这两个点中间的方点就是它们属于的点双。

所以如果 u,v 是兄弟，那么就属于 f_u 所代表的点双；如果 u 是 v 的爷爷，那么就属于 f_v 所代表的点双。

最后拿总方案数 n \choose 2 扣掉不合法方案数就可以了，复杂度 O(n + m)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 1000006
using namespace std;
int _,n,m,tp,dfs_clock,dn;
int dfn[N],tf[N],low[N],stk[N],col[N],fa[N],sz[N],cnt[N][2],c[N],vis[N];
long long ans;
vector<int> tG[N],bcc[N]; vector<pair<int,int> > G[N];
inline void add(int u,int v) {tG[u].push_back(v),tG[v].push_back(u);}
inline long long binom2(int x) {return 1ll*x*(x-1)/2;}
inline int find(int k) {return fa[k]==k?k:fa[k]=find(fa[k]);}
inline void merge(int u,int v) {u=find(u),v=find(v); if(u^v)fa[v]=u,sz[u]+=sz[v];}
inline int get(int u,int v)
{
    if(tf[u]==tf[v])return tf[u];
    else if(tf[tf[u]]==v)return tf[u];
    else if(tf[tf[v]]==u)return tf[v];
    assert(0);
}
void tarjan(int u)
{
    dfn[u]=low[u]=++dfs_clock,stk[++tp]=u;
    for(auto vv:G[u])if(!dfn[vv.first])
    {
        int v=vv.first;
        tarjan(v),low[u]=min(low[u],low[v]);
        if(low[v]==dfn[u])
        {
            dn++;
            for(int x=-1;x!=v;tp--)
                x=stk[tp],add(x,dn),bcc[dn].push_back(x);
            add(u,dn),bcc[dn].push_back(u);
        }
    } else low[u]=min(low[u],dfn[vv.first]);
}
void dfs(int u) {for(int v:tG[u])if(v!=tf[u])tf[v]=u,dfs(v);}
void solve(int o)
{
    for(int i=1;i<=dn;i++)fa[i]=i,sz[i]=0;
    for(int i=1;i<=n;i++)sz[i]=1;
    for(int i=n+1;i<=dn;i++)if(col[i]==o)
        for(int j:tG[i])merge(i,j);
    for(int i=1;i<=dn;i++)if(find(i)==i)ans-=binom2(sz[i]);
}
main()
{
    scanf("%d%d%d",&_,&n,&m),dn=n;
    for(int i=1,u,v;i<=m;i++)
    {
        char ch[3]; scanf("%d%d%s",&u,&v,ch+1);
        G[u].push_back({v,ch[1]=='d'});
        G[v].push_back({u,ch[1]=='d'});
    }
    ans=binom2(n),tarjan(1),dfs(1);
    for(int u=1;u<=n;u++)
        for(auto v:G[u])cnt[get(u,v.first)][v.second]++;
    for(int i=n+1;i<=dn;i++)
        if(!cnt[i][1])col[i]=0;
        else if(!cnt[i][0])col[i]=1; else col[i]=2;
    memset(cnt,0,sizeof(cnt));
    for(int u=1,b;u<=n;u++)
    {
        for(auto v:G[u])cnt[get(u,v.first)][v.second]++;
        for(auto v:G[u])
            if(!vis[b=get(u,v.first)]&&cnt[b][0]&&cnt[b][1])c[b]++,vis[b]=1;
        for(auto v:G[u])
        {
            vis[b=get(u,v.first)]=0;
            for(int i=0;i<2;i++)cnt[b][i]=0;
        }
    }
    for(int i=n+1;i<=dn;i++)if(c[i]==2)ans--;
    solve(0),solve(1);
    printf("%lld\n",ans);
    return 0;
}