CF競(jìng)賽題目講解_Tree Requests(樹上啟發(fā)式合并)
// 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為根 有根樹 帶點(diǎn)權(quán) 點(diǎn)權(quán)a到z 詢問rt子樹 深度為d的這層節(jié)點(diǎn) 點(diǎn)權(quán)重排能否構(gòu)成回文串
?
//暴力 -> 樹上啟發(fā)式合并
vector<int> g[maxn];
int cnt[maxn][30];//深度為i 字母為j的個(gè)數(shù)
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 順序編號(hào)
//輕重鏈剖分
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;//奇數(shù)個(gè)數(shù)
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 為查詢標(biāo)號(hào), 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;
}