相关链接
题目传送门：https://www.codechef.com/problems/BTREE
数据生成器：http://paste.ubuntu.com/23671176/
中文题面：http://www.codechef.com/download/translated/OCT14/mandarin/BTREE.pdf
官方题解：https://discuss.codechef.com/questions/53273/btree-editorial
神犇题解Ⅰ：http://xllend3.is-programmer.com/posts/64760.html
神犇题解Ⅱ：https://stalker-blog.apphb.com/post/divide-and-conquer-on-trees-based-on-vertexes
WJMZBMR Orz
又是 青年计算机科学家陈立杰 出的神题！
真的是跪烂！_(:з」∠)_
解题报告
看一看数据范围就可以知道这题复杂度一定只跟 ∑士兵数 相关
于是考虑先把虚树建出来，那么剩下的问题就是在利用虚树的边来统计答案了
1）函数式线段树的做法
考虑k=1，这样的话不用处理重复的问题，于是直接点分治就可以做
但现在有很多的点，于是我们可以将树剖成很多块，每块中恰好又一个城市a有卫兵
更进一步，我们规定这个联通块中任意一个点i到a的距离不大于到其他任意有卫兵的城市的距离
于是我们如果能在每一个联通块中单独处理每一个卫兵的话，就可以不用考虑去重的问题了
我们再仔细观察一下建出来的虚树，发现每一个块就是虚树上的一部分
对于a所在联通块深度最小的那个点，统计一下、加到答案里去
对于a所在联通块的其余边缘节点，再统计一下、从答案中减去
于是剩下的就是如何具体如何统计一条边对于答案的贡献了
我们分两种情况考虑：
- v不是u在虚树中的祖先，统计v的子树中、到u的距离为d的点的个数
这个的话，直接用函数式线段树查就好
- v是u的父亲，其余条件相同
这样的话，似乎与v的距离就不固定了（lca在u ~ v中移动）
于是先用点分治做出所有点到u的距离为d的点的个数n1
然后需要减掉v子树外的部分，这样的话，发现到v的距离就固定了
于是减掉所有点到v的距离为d-dis(u,v)的点数n2
再加上v子树中到v距离为d-dis(u,v)的点数n3就可以辣！
2）直接用点分治的做法
先用把点分树搞出来，这样就可以O(log^2(n))的时间复杂度内求dis(w,d)
其中dis(w,d)的定义为 到点w距离在d以内的点有多少 （不会的同学可以先去做BZOJ_3730）
再考虑把虚树建出来，这样的话唯一的问题就是如何去重了
考虑如果虚树上一条边的两个点的管辖范围没有交集，那么就肯定没有重复
如果有交集，那么设交集的重点为m，交集半径为r'那么直接减掉dis(m,r')就可以辣！
另外还需要预先将完全包含的管辖区间给修改成“相切”的情况，这样才能保证去重完整
还有的话，中点可能落在边上，于是可以在每边的中点加一个点
这样的做法是不是比主席树的做法清真了很多？
然而我还是写了5k+ _ (:з」∠) _
而且如果边带权的话，这题就很难这样做了
Code
最近为什么写啥常数都大到不行啊 QwQ
又是垫底…..
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100000 + 9;
const int M = N << 1;
const int INF = 1e8;
int n,m,T,head[N],to[M],nxt[M],num[N],cost[N];
int anc[N][18],dep[N],val[N],p[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline void Add_Edge(int u, int v) {
to[++T] = v; nxt[T] = head[u]; head[u] = T;
to[++T] = u; nxt[T] = head[v]; head[v] = T;
}
void DFS(int w, int f) {
static int cnt = 0;
dep[w] = dep[f] + 1;
anc[w][0] = f; num[w] = ++cnt;
for (int i=head[w];i;i=nxt[i]) {
if (!dep[to[i]]) {
DFS(to[i], w);
}
}
}
inline int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i=17;~i;i--)
if (dep[anc[x][i]] >= dep[y])
x = anc[x][i];
if (x == y) return x;
for (int i=17;~i;i--) {
if (anc[x][i] != anc[y][i]) {
x = anc[x][i];
y = anc[y][i];
}
}
return anc[x][0];
}
inline int dis(int x, int y) {
int lca = LCA(x, y);
return dep[x] + dep[y] - dep[lca] * 2;
}
class Point_Based_Divide_and_Conquer{
int fa[N][18],tot[N],sum[N];
int ans_tmp,root,block_size;
vector<int> q[N],mul[N];
bool vis[N];
public:
inline void init() {
block_size = n;
ans_tmp = INF;
Get_Root(1, 1);
tot[root] = 1;
build(root, n);
}
inline int query(int w, int rag) {
int ret = Query(w, rag, q);
for (int i=1,t;i<tot[w];i++) {
t = rag - dis(fa[w][i], w);
if (t >= 0) {
ret += Query(fa[w][i], t, q);
ret -= Query(fa[w][i-1], t, mul);
}
}
return ret;
}
private:
void Get_Root(int w, int f) {
int mx = 0; sum[w] = 1;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
mx = max(mx, sum[to[i]]);
sum[w] += sum[to[i]];
}
}
mx = max(block_size - sum[w], mx);
if (mx < ans_tmp) {
ans_tmp = mx;
root = w;
}
}
void build(int w, int sz) {
vis[w] = 1; fa[w][0] = w;
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
block_size = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
ans_tmp = INF; Get_Root(to[i], w);
memcpy(fa[root]+1, fa[w], sizeof(fa[w])-sizeof(int));
tot[root] = tot[w] + 1;
build(root, block_size);
}
}
if (val[w]) {
for (int i=0;i<tot[w];i++)
q[fa[w][i]].push_back(dis(w, fa[w][i]));
for (int i=0;i<tot[w]-1;i++)
mul[fa[w][i]].push_back(dis(w, fa[w][i+1]));
}
sort(q[w].begin(), q[w].end());
sort(mul[w].begin(), mul[w].end());
}
inline int Query(int w, int r, vector<int> *a) {
return upper_bound(a[w].begin(), a[w].end(), r) - a[w].begin();
}
}PDC;
class Virtual_Tree{
int stk[N],rag[N],top,lca,cnt,root;
queue<int> que;
bool inq[N];
public:
inline void build(int &tot) {
cnt = tot; T = 0;
root = p[1] = read();
newnode(p[1], read());
for (int i=2;i<=tot;i++) {
p[i] = read();
newnode(p[i], read());
root = LCA(root, p[i]);
}
static auto cmp = [](int a, int b) {return num[a] < num[b];};
sort(p+1, p+1+tot, cmp);
if (root != p[1]) p[++tot] = root, newnode(root, -1);
stk[top=1] = root;
for (int i=1+(p[1]==root);i<=cnt;i++) {
lca = LCA(p[i], stk[top]);
for (;dep[stk[top]] > dep[lca];top--)
if (dep[stk[top-1]] >= dep[lca]) AddEdge(stk[top-1], stk[top]);
else newnode(lca, -1), AddEdge(lca, stk[top]);
if (lca != stk[top])
stk[++top] = p[++tot] = lca;
if (p[i] != stk[top])
stk[++top] = p[i];
}
for (int i=1;i<top;i++)
AddEdge(stk[i], stk[i+1]);
}
inline int solve(int tot) {
prework(tot);
int ret = 0;
for (int i=1,u,v,r,mid,t;i<T;i+=2) {
u = to[i]; v = to[i+1];
r = rag[u] + rag[v] - cost[i] >> 1;
if (r >= 0) {
mid = move(u, v, r);
ret -= PDC.query(mid, r);
}
}
for (int i=1;i<=tot;i++)
ret += PDC.query(p[i], rag[p[i]]);
return ret;
}
private:
inline void newnode(int w, int v) {
rag[w] = v << 1;
head[w] = 0;
}
inline int move(int x, int y, int r) {
if (dep[x] < dep[y]) swap(x, y);
r = rag[x] - r;
for (int i=0;r;i++,r>>=1)
if (r & 1) x = anc[x][i];
return x;
}
inline void prework(int tot) {
for (int i=1;i<=tot;i++) {
que.push(p[i]);
inq[p[i]] = 1;
}
while (!que.empty()) {
int w = que.front();
que.pop(); inq[w] = 0;
for (int i=head[w];i;i=nxt[i]) {
if (rag[w] > rag[to[i]] + cost[i]) {
rag[to[i]] = rag[w] - cost[i];
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
}
inline void AddEdge(int u, int v) {
int w = dis(u, v);
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}
}VT;
int main() {
n = read();
fill(val+1, val+1+n, 1);
for (int i=1,lim=n,u,v;i<lim;i++) {
u = read(); v = read();
Add_Edge(u, ++n);
Add_Edge(n, v);
}
DFS(1, 1);
for (int j=1;j<=17;j++) {
for (int i=1;i<=n;i++) {
anc[i][j] = anc[anc[i][j-1]][j-1];
}
}
PDC.init();
m = read();
for (int y=1,k;y<=m;y++) {
VT.build(k = read());
printf("%d\n",VT.solve(k));
}
return 0;
}
