题意
题目链接
Sol
很神仙的题
我们考虑询问(a, b)(a是b的祖先)，直接对b根号分治
如果b的出现次数(< sqrt{n})，我们可以直接对每个b记录下与它有关的询问，这样每个询问至多扫(sqrt{n})个点即可知道答案，那么dfs的时候暴力统计答案即可，复杂度(qsqrt{n})
如果b的出现次数(> sqrt{n})，显然这样的b最多只有(sqrt{n})个，也就是说在询问中最多会有(sqrt{n})个这样的b，那么我们可以对每个a，暴力统计，复杂度(nsqrt{n})
然后用天天爱跑步那题的差分技巧搞一下就行了
代码十分好写~
代码语言：javascript复制#include<bits/stdc .h>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long
#define LL long long
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e6 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
int N, R, Q, base;
vector<int> v[MAXN];
vector<Pair> a1[MAXN], a2[MAXN];
int r[MAXN], fa[MAXN], ti[MAXN], ha[MAXN], ans[MAXN];
void dfs1(int x) {
for(auto &a : a1[r[x]]) ans[a.se] = ha[a.fi]; ha[r[x]] ;
for(auto &to : v[x]) dfs1(to); ha[r[x]]--;
}
void dfs2(int x) {
for(auto &b: a2[r[x]]) ans[b.se] -= ha[b.fi];
for(auto &to: v[x]) dfs2(to);
for(auto &b: a2[r[x]]) ans[b.se] = ha[b.fi];
ha[r[x]] ;
}
signed main() {
// Fin(9); Fout(b);
N = read(); R = read(); Q = read(); base = sqrt(N);
r[1] = read(); ti[r[1]] ;
for(int i = 2; i <= N; i ) {
int f = read(); r[i] = read();
v[f].push_back(i);
ti[r[i]] ;
}
for(int i = 1; i <= Q; i ) {
int a = read(), b = read();
if(ti[b] < base) {
a1[b].push_back({a, i});
} else {
a2[a].push_back({b, i});
}
}
dfs1(1);
memset(ha, 0, sizeof(ha));
dfs2(1);
for(int i = 1; i <= Q; i ) printf("%dn", ans[i]);
return 0;
}
