[Codeforces] 208E. Blood Cousins
題目連結: http://codeforces.com/problemset/problem/208/E 稍微轉化一下問題就可以得到問節點$i$的子節點們深度為$d$的有那些，轉法也很簡單，對於一組詢問$(v, p)$就直接變成，對於$v$的$p$倍祖先問在$dep[v]$的數字有哪些(問一個人的$p$倍祖先可以直接用個倍增法做到)。轉化成這樣後就可以直接開個map維護每個深度為$k$時有幾個，然後要合併兩子樹就啟發式合併就好了。 #include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
typedef pair<int,int> PII;
#define PB push_back
#define FF first
#define SS second
class K_anc{
private:
vector<int> G[N];
int anc[N][20];
void dfs(int w, int f){
anc[w][0]=f;
for(auto i: G[w]) if(i!=f)
dfs(i, w);
}
public:
inline void AddEdge(int u, int v){
G[u].PB(v);
G[v].PB(u);
}
void solve(int r, int maxn){
dfs(r, r);
for(int j=1;j<20;j++) for(int i=0;i<maxn;i++){
anc[i][j] = anc[anc[i][j-1]][j-1];
...