题解 | #小红的树#

小红的树

http://www.nowcoder.com/practice/66ab364d3fba487eb39bd3460fd484c0

小红的树

难度:2星

树形dp模板题。我们先预处理出每个节点子树的红色节点的数量。定义 dp[i]dp[i] 为以 ii 为根的子树的红色节点的数量,那么转移方程是:

dp[i]=xidp[x]+[i]dp[i]=\sum_{x是i的孩子}dp[x]+[i为红点]

只需要在dfs的时候进行转移即可。

#include<bits/stdc++.h>
using namespace std;
vector<int>g[100020];
int dp[100010];
string s;
int dfs(int x){
    int i,sum=s[x-1]=='R';
    for(i=0;i<g[x].size();i++){
        sum+=dfs(g[x][i]);
    }
    return dp[x]=sum;
}
int main(){
    int n,i;
    cin>>n;
    for(i=2;i<=n;i++){
        int x;
        cin>>x;
        g[x].push_back(i);
    }

    cin>>s;
    dp[1]=dfs(1);
    int q;
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        cout<<dp[x]<<endl;
    }

}



全部评论

相关推荐

01-14 19:01
吉首大学 Java
黑皮白袜臭脚体育生:加个项目吧,一般需要两个项目一业务一轮子呢,简历统一按使用了什么技术实现了什么功能解决了什么问题或提升了什么性能指标来写
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务