牛课字符路径类似树形dp

朴灿烈づ我的快乐病毒、 2022-05-16 08:37 112阅读 0赞

[传送门][Link 1]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef unsigned int ui;
    const ll INF=0x3f3f3f3f3f3f3f3f;
    const int N=2e5+10;
    int n, m;
    struct node{
        int v;
        char ch;
    };
    vector<node> G[N];
    ui dp[N][4];//0=空格联通的节点数,1='.',2='a'~'z', 3='A'~'Z';
    ui ans;
    bool vis[N];
    
    void dfs(int u){
        if(vis[u]) return;
        dp[u][0]=1; vis[u]=1;
        for(int i=0; i<G[u].size(); i++){
            node it=G[u][i];
            dfs(it.v);
    
            if(it.ch=='_')
                for(int j=0; j<4; j++) dp[u][j]+=dp[it.v][j];
            else if(it.ch=='.')
                dp[u][1]+=dp[it.v][0];
            else if(islower(it.ch))
                dp[u][2]+=(dp[it.v][2]+dp[it.v][1]);
            else
                dp[u][3]+=(dp[it.v][2]+dp[it.v][1]);
        }
    }
    
    int main(){
        scanf("%d%d", &n, &m);
        int u, v; char ch;
        for(int i=1; i<=m; i++){
            scanf("%d%d %c", &u, &v, &ch);
            G[u].push_back((node){v, ch});
        }
    
        for(int i=1; i<=n; i++)
            dfs(i), ans+=dp[i][3];
    
        printf("%u\n", ans);
    
        return 0;
    }

[Link 1]: https://www.nowcoder.com/acm/contest/160/B

发表评论取消回复

表情：

评论列表（有 0 条评论，112人围观）

还没有评论，来说两句吧...

相关阅读

相关【树形DP+换根思想】2022牛客多校加赛 H

[登录—专业IT笔试面试备考平台\_牛客网][IT] 题意： ![4acbe231ccfb46d99ee831d13a667218.png][] ![7cdb215a69

àì夳堔傛蜴生んèń/ 2024年03月23日 17:21/ 0 赞/ 35 阅读

相关树形dp1

没有上司的舞会，树形dp include<bits/stdc++.h> define mms(a) memset(a,-1,sizeof(a)) u

超、凢脫俗/ 2023年08月17日 16:36/ 0 赞/ 89 阅读

相关动态规划-树形DP

文章目录树形DP HDU-1520 HDU-2196 树形DP -------------------- 树形DP，顾名思义是在「树」这种数

淩亂°似流年/ 2023年03月04日 06:40/ 0 赞/ 165 阅读

相关 1072 树的最长路径（树形dp）

1. 问题描述：给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。现在请你找到树中的一条最长路径。换句话说，要找到一条路径，使得路径两

￡神魔★判官ぃ/ 2022年08月28日 11:48/ 0 赞/ 6 阅读

相关牛课字符路径类似树形dp

[传送门][Link 1] include<bits/stdc++.h> using namespace std; typedef long long

朴灿烈づ我的快乐病毒、/ 2022年05月16日 08:37/ 0 赞/ 113 阅读

相关浅谈树形dp

总结：这一周重点训练了树形dp。对树形dp也有了一定的认识。先说一下总的观点吧。树形dp一般无非就是求出子节点的状态从而进一步去更新根节点的状态。一般的话，

系统管理员/ 2022年02月09日 10:53/ 0 赞/ 313 阅读

相关 uva10859 (树形dp)

题意：给你一个ｎ个点ｍ条边的无向无环图，在尽量少的节点上放灯，使得所有边都被照亮。每盏灯将照亮以它为一个端点的所有边。在灯的总数最小的前提下，被两盏灯同时被照亮的边数应该尽量

青旅半醒/ 2021年12月14日 03:21/ 0 赞/ 286 阅读

相关 HDU - 2196（树形DP）

题目： A school bought the first computer some time ago(so this computer's id is 1). Durin

快来打我*/ 2021年11月26日 09:38/ 0 赞/ 271 阅读

相关牛牛与数组DP

链接：[https://ac.nowcoder.com/acm/problem/21738][https_ac.nowcoder.com_acm_problem_21738]

缺乏、安全感/ 2021年11月16日 23:08/ 0 赞/ 294 阅读

相关偷天换日（树形DP）

[洛谷][Link 1] 比较喜欢(≧∇≦)ﾉ这个建图对于叶子节点，直接处理出f\[i\]\[j\]当前i号节点分j个时间 include<bits/stdc

Dear 丶/ 2021年11月09日 08:04/ 0 赞/ 254 阅读