Wannafly挑戰賽22 B 字元路徑

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn=50000+100;
const LL mod=1LL<<32;

struct Edge{
    
    int to,next;
    char val;
}edge[maxn];
int head[maxn],tot;

LL dp[maxn][4];
bool vis[maxn];

void DFS(int u){
    
    if(vis[u]) return ;
    dp[u][0]=1;vis[u]=true;
    for(int i=head[u];i!=-1;i=edge[i].next){
        
        Edge e=edge[i];
        int v=e.to;
        DFS(v);
        if(e.val=='_') for(int j=0;j<=3;j++) dp[u][j]+=dp[v][j];
        else if(e.val=='.') dp[u][1]+=dp[v][0];
        else if(islower(e.val)) dp[u][2]+=(dp[v][1]+dp[v][2]);
        else dp[u][3]+=(dp[v][1]+dp[v][2]);
    }
}

int main(){
    
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        
        head[i]=-1;
        vis[i]=false;
        dp[i][0]=dp[i][1]=dp[i][2]=dp[i][3]=0;
    }
    tot=0;
    for(int i=1;i<=m;i++){
        
        int u,v;
        char val;
        scanf("%d%d %c",&u,&v,&val);
        edge[tot].to=v;
        edge[tot].val=val;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    LL ans=0;
    for(int i=1;i<=n;i++) DFS(i),ans+=dp[i][3],ans%=mod;
    printf("%lld\n",ans);
}