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;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 18:27
天津大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-11 21:41
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议