非树形DP做法

知识点：DFS序维护子树信息，前缀和

由于DFS过程是遍历当前节点的全部子节点后返回当前节点，所以利用这个性质可以有效维护子树信息。

DFS过程中使用一个时间戳 $dfndfn$ 并记录进入某个节点的时间 $inin$ 和出这个节点的时间 $outout$ 。我们记录一个DFS序数组记录所有节点，即 $dfndfn$ 数组，（并不一定需要真正创建这个数组）， $[df{n}_{in},df{n}_{out}][dfn\_\{in\}\; ,\; dfn\_\{out\}]$ 即是 $inin$ 节点的子树范围。我们只需将 $colorcolor$ 数组映射到 $dfndfn$ 数组即可使用前缀和维护某个节点的全部子树节点。

具体实现方法如代码。

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9+7;

vector<int> g[110000];
int col[110000] , in[110000] , out[110000] , dfn = 0 , n;

void dfs(int x) {
    in[x] = ++dfn;
    for (auto nxt : g[x]) {
        dfs(nxt);
    }
    out[x] = dfn;
}

int main() {
    scanf("%d",&n);
    for (int i = 2 ; i <= n ; i ++) {
        int fa;
        scanf("%d",&fa);
        g[fa].push_back(i);
    }
    dfs(1);
    for (int i = 1 ; i <= n ; i ++) {
        char c;
        scanf("%c",&c);
        while (c == '\n' || c == ' ')scanf("%c",&c);
        if (c=='R') {
            col[in[i]] = 1;
        }
    }
    for (int i = 1 ; i <= n ; i ++) {
        col[i] = col[i]+col[i-1];
    }
    int q;
    scanf("%d",&q);
    while (q --) {
        int x;
        scanf("%d",&x);
        printf("%d\n",col[out[x]]-col[in[x]-1]);
    }
}