题目链接

CF570D

题解

复习dsu on tree
就是基于树剖均摊O(nlogn)的暴力
这题维护每一层的各个字母数量的奇偶性就行了

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
#define ls (u << 1)
#define rs (u << 1 | 1)
using namespace std;
const int maxn = 500005,maxm = 1000005,INF = 0x3f3f3f3f;
inline int read(){
    int out = 0,flag = 1; char c = getchar();
    while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
    while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
    return flag ? out : -out;
}
char s[maxn];
int N,M,h[maxn],ne;
struct EDGE{
    int to,nxt;
}ed[maxm];
int q[maxn],qi;
struct Query{
    int id,h,nxt;
}Q[maxn];
void add(int u,int id,int H){
    Q[++qi] = (Query){id,H,q[u]}; q[u] = qi;
}
void build(int u,int v){
    ed[++ne] = (EDGE){v,h[u]}; h[u] = ne;
    ed[++ne] = (EDGE){u,h[v]}; h[v] = ne;
}

int fa[maxn],son[maxn],siz[maxn],dep[maxn],c[maxn];
void dfs1(int u){
    siz[u] = 1; dep[u] = dep[fa[u]] + 1;
    for (int k = h[u],to; k; k = ed[k].nxt)
        if ((to = ed[k].to) != fa[u]){
            fa[to] = u;
            dfs1(to);
            siz[u] += siz[to];
            if (!son[u] || siz[to] > siz[son[u]]) son[u] = to;
        }
}
int ans[maxn];
int sum[maxn][26],odd[maxn];
void upd(int u,int v){
    sum[dep[u]][c[u]] += v;
    if (sum[dep[u]][c[u]] & 1) odd[dep[u]]++;
    else odd[dep[u]]--;
}
void cal(int u,int v){
    upd(u,v);
    Redge(u) if ((to = ed[k].to) != fa[u]) cal(to,v);
}
void dfs(int u){
    Redge(u) if ((to = ed[k].to) != fa[u] && to != son[u]) dfs(to);
    if (son[u]) dfs(son[u]);
    upd(u,1);
    Redge(u) if ((to = ed[k].to) != fa[u] && to != son[u]) cal(to,1);
    for (int k = q[u]; k; k = Q[k].nxt)
        ans[Q[k].id] = (odd[Q[k].h] <= 1) ? true : false;
    if (son[fa[u]] != u) cal(u,-1);
}
int main(){
    N = read(); M = read();
    for (int i = 2; i <= N; i++) build(i,read());
    scanf("%s",s + 1);
    for (int i = 1; i <= N; i++) c[i] = s[i] - 'a';
    for (int i = 1; i <= M; i++){
        int u = read(),H = read();
        add(u,i,H);
    }
    dfs1(1);
    dfs(1);
    for (int i = 1; i <= M; i++) puts(ans[i] ? "Yes" : "No");
    return 0;
}

这里丢一个dsu on tree的板子

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
#define ls (u << 1)
#define rs (u << 1 | 1)
using namespace std;
const int maxn = 100005,maxm = 400005,INF = 0x3f3f3f3f;
inline int read(){
    int out = 0,flag = 1; char c = getchar();
    while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
    while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
    return flag ? out : -out;
}
int N,h[maxn],ne;
struct EDGE{
    int to,nxt;
}ed[maxm];
void build(int u,int v){
    ed[++ne] = (EDGE){v,h[u]}; h[u] = ne;
    ed[++ne] = (EDGE){u,h[v]}; h[v] = ne;
}
int fa[maxn],son[maxn],siz[maxn],c[maxn];
void dfs1(int u){
    siz[u] = 1;
    for (int k = h[u],to; k; k = ed[k].nxt)
        if ((to = ed[k].to) != fa[u]){
            fa[to] = u;
            dfs1(to);
            siz[u] += siz[to];
            if (!son[u] || siz[to] > siz[son[u]]) son[u] = to;
        }
}
LL ans[maxn],bac[maxn];
LL mx,Ans;
void upd(int u,int v){
    bac[c[u]] += v;
    if (v < 0) return;
    if (bac[c[u]] == mx) Ans += c[u];
    else if (bac[c[u]] > mx) mx = bac[c[u]],Ans = c[u];
}
void cal(int u,int v){
    upd(u,v);
    Redge(u) if ((to = ed[k].to) != fa[u]) cal(to,v);
}
void dfs(int u){
    Redge(u) if ((to = ed[k].to) != fa[u] && to != son[u]) dfs(to);
    if (son[u]) dfs(son[u]);
    upd(u,1);
    Redge(u) if ((to = ed[k].to) != fa[u] && to != son[u]) cal(to,1);
    ans[u] = Ans;
    if (son[fa[u]] != u) cal(u,-1),Ans = mx = 0;
}
int main(){
    N = read();
    REP(i,N) c[i] = read();
    for (int i = 1; i < N; i++) build(read(),read());
    dfs1(1);
    dfs(1);
    for (int i = 1; i <= N; i++) printf("%I64d ",ans[i]);
    return 0;
}