CF竞赛题目讲解_Tree Requests(树上启发式合并)

// https://codeforces.com/problemset/problem/570/D

 

#include "stdafx.h"

//#include <bits/stdc++.h>

#include <algorithm> 

#include <vector> 

using namespace std;

#define ll long long

#define pii pair<int, int>

const int maxn = 5e5 + 10;

//1为根 有根树 带点权 点权a到z 询问rt子树 深度为d的这层节点 点权重排能否构成回文串

 

//暴力 -> 树上启发式合并

vector<int> g[maxn];

int cnt[maxn][30];//深度为i 字母为j的个数

int son[maxn],siz[maxn],dep[maxn];

char col[maxn]="\0zacccd";

vector<pii> q[maxn];

bool ans[maxn];

int L[maxn],V[maxn],T=0;//  dfs 顺序编号

//轻重链剖分

void dfs(int rt) 

{

siz[rt]=1;

V[L[rt]=++T]=rt;

for(int &i:g[rt]) 

{

dep[i]=dep[rt]+1;

dfs(i);

if(siz[i] > siz[son[rt]]) son[rt]=i;

siz[rt]+=siz[i];

}

}

bool check(int d) //check深度为d  字母分布情况

{

int odd=0;//奇数个数

for(int i=1;i<=26;i++) 

{

odd+=(cnt[d][i]&1);

}

return odd<=1;

}

void dfs2(int rt,bool ok) 

{

for(auto i:g[rt]) 

{

if(i==son[rt]) continue;

dfs2(i,0);

}

if(son[rt]) dfs2(son[rt],1);

for(auto k:g[rt]) 

{

if(k==son[rt]) continue;

for (int i=0; i<siz[k]; i++) 

{

int id=col[V[L[k]+i]]-'a'+1;

cnt[dep[V[L[k]+i]]][id]+=1;

}

}

int id=col[rt]-'a'+1;

cnt[dep[rt]][id]+=1;

for(auto i:q[rt]) 

{   //  i.second 为查询标号， i.first 为查询深度

ans[i.second]=check(i.first);

} 

if(!ok) //是轻儿子 clear

for (int i=0; i<siz[rt]; i++) 

{

id=col[V[L[rt]+i]]-'a'+1;

cnt[dep[V[L[rt]+i]]][id]-=1;

}

}

int n,m;

int main()

{

n=6,m=5;

// scanf("%d %d",&n,&m);,

int fa;

int faa[8]={1 ,1, 1, 3 ,3};

for(int i=2;i<=n;i++) 

{

//int fa;scanf("%d",&fa);

fa=faa[i-2];

g[fa].push_back(i);

}

//scanf("%s",col+1);

dep[1]=1;

dfs(1);

int qq[32][2]={

1 ,1,

3 ,3,

4, 1,

6, 1,

1, 2};

for(int i=1;i<=m;i++) 

{

int u,d;

//scanf("%d %d",&u,&d);

u=qq[i-1][0];

d=qq[i-1][1];

q[u].push_back(make_pair (d,i));

}

dfs2(1,1);

for(int i=1;i<=m;i++) 

if(ans[i]) puts("Yes");

else puts("No");

return 0;

}