CF竞赛题目讲解_CF208E(树上启发式合并+倍增)
// https://codeforces.com/problemset/problem/208/E
#include "stdafx.h"
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N=100010;
int n,m;
int acc[N][25],siz[N],dep[N],son[N];
int cnt[N],len = 16; //森林深度最大值, CF测试15错误
int anw[N];
std::vector<int > tr;
std::vector<pii > v[N];
std::vector<int > e[N];
void dfs1(int now,int p)
{
dep[now] = dep[p]+1; cout<<"now="<<now<<", dep[now]="<<dep[now] <<endl;
acc[now][0] = p;// father
siz[now] = 1; // 子树大小
for(int i=1;(1<<i)<=dep[now];i++){
acc[now][i] = acc[acc[now][i-1]][i-1]; //2^i级祖先就是2^(i-1)级祖先的2^(i-1)祖先
cout<<", i="<<i<<", 1<<i="<<(1<<i)<<", 1="<<1<<endl;
}
for(auto spot:e[now])
{
if(spot==p) continue;
dfs1(spot,now);
siz[now] += siz[spot];// 子树大小
if(siz[son[now]]<siz[spot]) son[now] = spot;// 重儿子
}
}
void add(int now,int p,int value,int wson)
{
cnt[dep[now]] += value;// 假设now的dep[now]-1代祖先为x，则x的dep[now]-1代子孙个数加1
for(auto spot:e[now])
{
if(spot==p||spot==wson) continue;
add(spot,now,value,wson);
}
}
void dfs(int now,int p,int keep)
{
for(auto spot:e[now])
{
if(spot==p||spot==son[now]) continue;
dfs(spot,now,0);
}
if(son[now]) dfs(son[now],now,1);
add(now,p,1,son[now]);
for(auto t:v[now])
{
int x = t.first,id = t.second;
anw[id] = cnt[dep[now]+x]-1; //now 的x代子孙个数cnt[dep[now]+x]，减去他本身这个点，即为表亲个数
cout<<"id="<<id<<", dep[now]+x= "<<dep[now]+x<<endl;
}
if(!keep) add(now,p,-1,0);
}
signed main()
{
//cin>>n;
n=9;
int X[16] ={0, 1, 1 ,0 ,4 ,4,5,6,6};
for(int i=1;i<=n;i++)
{
int x;
//cin>>x;
x=X[i-1];
if(x) e[i].pb(x),e[x].pb(i);
else tr.pb(i);
}
for(auto t:tr) dfs1(t,0);
//cin>>m;
m=8;
int QU[8][2]={
1, 1,
1 ,2,
2, 1,
2 ,2,
4 ,1,
5, 1,
6 ,1,
7,2};
for(int i=1;i<=m;i++)
{
int a,b;
//cin>>a>>b;
a=QU[i-1][0];
b=QU[i-1][1];
for(int j=len;j>=0;j--)
{ // 如果b=7=2^2+2^1+2^0, 则3次可以倍增到7代祖先
if(b>>j&1) a = acc[a][j]; //倍增到b代祖先， acc[a][j]代表a的2的j次方祖先。
}
v[a].pb(make_pair(b,i));
}
for(auto t:tr) dfs(t,0,0);
for(int i=1;i<=m;i++) cout<<anw[i]<<" \n"[i==m];
return 0;
}
