Tree Requests（Update）

感受



更新

思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;//1061109567 大约1e9
const ll INF = 0x3f3f3f3f3f3f3f3f;//4557430888798830399 大约4e18 且INF + INF < long long最大值
const int maxn = 5e5 + 10;
int n, q, dfn;
int in[maxn], out[maxn];
int s[maxn];
struct node{
    int id;
    int x;
};
vector<node> d[maxn];
vector<int> G[maxn];
vector<int> h[2];
vector<int> num[2][30];
bool ans[maxn];
void add_edge(int u, int v){
    G[u].push_back(v);
}
void dfs(int u){
    in[u] = ++dfn;
    for(auto v : G[u]){
        dfs(v);
    }
    out[u] = dfn;
}
int get(int l, int r){
    int gg = 0;
    for(int i = 0; i < 26; i++){
        int sum = num[0][i][r] - (l == 0 ? 0 : num[0][i][l - 1]);
        if(sum & 1) gg++;
    }
    return gg;
}
bool check(int u){
    int l, r;
    l = lower_bound(h[0].begin(), h[0].end(), in[u]) - h[0].begin();
    r = upper_bound(h[0].begin(), h[0].end(), out[u]) - h[0].begin(); r--;
    if(l > r) return true;
    int len = r - l + 1;
    int gg = get(l, r);
    if(len & 1) return gg == 1;
    return gg == 0;
}
void solve(int dep){
    if(dep == 1) return ;
    for(auto it : d[dep]){
        ans[it.id] = check(it.x);
    }

}
void bfs(int u){
    queue<pii> q;
    q.push(make_pair(u, 1)); int dep = 1;
    while(!q.empty()){
        pii tmp = q.front(); q.pop();
        if(tmp.second != dep){
            solve(dep);
            for(int i = 0; i < 26; i++){
                num[0][i] = num[1][i];
                num[1][i].clear();
            }
            h[0] = h[1];
            h[1].clear();
            dep++;
        }///处理dep深度的数据
        for(auto v : G[tmp.first]){
            q.push(make_pair(v, tmp.second + 1));
            h[1].push_back(in[v]);
            for(int i = 0; i < 26; i++){
                if(num[1][i].empty()) num[1][i].push_back(s[v] == i);
                else num[1][i].push_back(num[1][i].back() + (s[v] == i));
            }
        }
    }
    solve(dep);
}
int main(){
    scanf("%d%d", &n, &q);
    int u, x;
    for(int i = 2; i <= n; i++){
        scanf("%d", &u);
        add_edge(u, i);
    }
    string t; cin >> t;
    for(int i = 0; i < t.size(); i++){
        s[i + 1] = t[i] - 'a';
    }
    dfs(1);
    for(int i = 1; i <= q; i++){
        scanf("%d%d", &u, &x);
        d[x].push_back((node){i, u});
        ans[i] = true;
    }
    bfs(1);
    for(int i = 1; i <= q; i++){
        if(ans[i]) puts("Yes");
        else puts("No");
    }
    return 0;
}

Dsu on tree

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define ls o << 1
#define rs o << 1 | 1
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;//1061109567 大约1e9
const ll INF = 0x3f3f3f3f3f3f3f3f;//4557430888798830399 大约4e18 且INF + INF < long long最大值
const int maxn = 5e5 + 10;
struct edge{
    int v, nex;
}e[maxn << 1];
char s[maxn];
int f[maxn];
int head[maxn], cnt, m, n;
int son[maxn], siz[maxn];
int num[maxn][30];
int len[maxn], dep[maxn];
bool ans[maxn];
struct node{
    int id; int h;
};
vector<node> a[maxn];
void init(){
    cnt = 0;
    for(int i = 0; i <= n; i++){
        head[i] = -1;
    }
}
void add_edge(int u, int v){
    e[cnt] = (edge){v, head[u]};
    head[u] = cnt++;
}
void dfs1(int u, int fa, int d){
    int v; dep[u] = d;
    siz[u] = 1;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == fa) continue;
        dfs1(v, u, d + 1);
        siz[u] += siz[v];
        if(siz[son[u]] < siz[v]) son[u] = v;
    }
}
void update1(int u, int fa, int p){
    int v;
    len[dep[u]]++; num[dep[u]][f[u]]++;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == fa || v == p) continue;
        update1(v, u, p);
    }
}
void update2(int u, int fa){
    int v;
    len[dep[u]]--; num[dep[u]][f[u]]--;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == fa) continue;
        update2(v, u);
    }
}
bool check(int u, int h){
    int pa = 0;
    for(int i = 0; i < 26; i++){
        if(num[h][i] & 1) pa++;
    }
    if(len[h] & 1){
        return pa == 1;
    }
    else return pa == 0;
}
void solve(int u){
    int id; int h;
    for(auto it : a[u]){
        id = it.id; h = it.h;
        ans[id] = check(u, h);
    }
}
void dfs2(int u, int fa, int del){
    int v;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == fa || v == son[u]) continue;
        dfs2(v, u, 1);
    }
    if(son[u]){
        dfs2(son[u], u, 0);
    }
    update1(u, fa, son[u]);
    solve(u);
    if(del){
        update2(u, fa);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    init();
    int u, v;
    for(int i = 2; i <= n; i++){
        scanf("%d", &v);
        add_edge(i, v);
        add_edge(v, i);
    }
    scanf("%s", s + 1);
    for(int i = 1; i <= n; i++){
        f[i] = s[i] - 'a';
    }
    dfs1(1, 0, 1);
    for(int i = 1; i <= m; i++){
        scanf("%d%d", &u, &v);
        a[u].push_back((node){i, v});
    }
    dfs2(1, 0, 0);
    for(int i = 1; i <= m; i++){
        if(ans[i]) puts("Yes");
        else puts("No");
    }
    return 0;
}