[BZOJ3572][Hnoi2014]世界树
试题描述
世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。
世界树的形态可以用一个数学模型来描述：世界树中有n个种族，种族的编号分别从1到n，分别生活在编号为1到n的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连，道路的长度为1。保证连接的方式会形成一棵树结构，即所有的聚居地之间可以互相到达，并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度；例如，若聚居地a和b之间有道路，b和c之间有道路，因为每条道路长度为1而且又不可能出现环，所卧a与c之间的距离为2。
出于对公平的考虑，第i年，世界树的国王需要授权m[i]个种族的聚居地为临时议事处。对于某个种族x（x为种族的编号），如果距离该种族最近的临时议事处为y（y为议事处所在聚居地的编号），则种族x将接受y议事处的管辖（如果有多个临时议事处到该聚居地的距离一样，则y为其中编号最小的临时议事处）。
现在国王想知道，在q年的时间里，每一年完成授权后，当年每个临时议事处将会管理多少个种族（议事处所在的聚居地也将接受该议事处管理）。 现在这个任务交给了以智慧著称的灵长类的你：程序猿。请帮国王完成这个任务吧。
世界树的形态可以用一个数学模型来描述：世界树中有n个种族，种族的编号分别从1到n，分别生活在编号为1到n的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连，道路的长度为1。保证连接的方式会形成一棵树结构，即所有的聚居地之间可以互相到达，并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度；例如，若聚居地a和b之间有道路，b和c之间有道路，因为每条道路长度为1而且又不可能出现环，所卧a与c之间的距离为2。
出于对公平的考虑，第i年，世界树的国王需要授权m[i]个种族的聚居地为临时议事处。对于某个种族x（x为种族的编号），如果距离该种族最近的临时议事处为y（y为议事处所在聚居地的编号），则种族x将接受y议事处的管辖（如果有多个临时议事处到该聚居地的距离一样，则y为其中编号最小的临时议事处）。
现在国王想知道，在q年的时间里，每一年完成授权后，当年每个临时议事处将会管理多少个种族（议事处所在的聚居地也将接受该议事处管理）。 现在这个任务交给了以智慧著称的灵长类的你：程序猿。请帮国王完成这个任务吧。
输入
第一行为一个正整数n，表示世界树中种族的个数。
接下来n-l行，每行两个正整数x，y，表示x聚居地与y聚居地之间有一条长度为1的双
向道路。接下来一行为一个正整数q，表示国王询问的年数。
接下来q块，每块两行：
第i块的第一行为1个正整数m[i]，表示第i年授权的临时议事处的个数。
第i块的第二行为m[i]个正整数h[l]、h[2]、…、h[m[i]]，表示被授权为临时议事处的聚居地编号（保证互不相同）。
输出
输出包含q行，第i行为m[i]个整数，该行的第j(j=1，2…，，m[i])个数表示第i年被授权的聚居地h[j]的临时议事处管理的种族个数。
输入示例
10 2 1 3 2 4 3 5 4 6 1 7 3 8 3 9 4 10 1 5 2 6 1 5 2 7 3 6 9 1 8 4 8 7 10 3 5 2 9 3 5 8
输出示例
1 9 3 1 4 1 1 10 1 1 3 5 4 1 3 1 1
数据规模及约定
N<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000
题解
建出虚树后 dp 求出距离虚树上每个点最近的议事点在哪以及到它的距离。
然后考虑虚树上每条边对两个端点所对应的议事点的答案的贡献，不妨设两个端点分别为 a 和 b，边长为 d，a 到它最近的议事点距离为 f[a]，b 到它最近的议事点距离为 f[b]，那么需要求这么一个 x 使得 f[a] + x = f[b] + (d - x)，解得 x = [(f[b] - f[a] + d) / 2]（向下取整）。这个 x 是干什么的呢？就是从 b 在原树中向上走 x 单位的长度所经过的点的议事点都是 b 所对应的议事点（因为这些点离 b 更近），在往上的点就该去 a 了，注意当 (f[b] - f[a] + d) 为偶数时，会有一个正中间的点，即到 a 和到 b 的距离相等，这时记得特判一下。我们把 b 向上 x 个单位的点设为 mid。那么这条边对于 b 的贡献为 siz[mid] - siz[b]，对于 a 的贡献为 siz[son] - siz[mid]，其中 son 是 a, b 路径上 a 的第一个儿子，siz[u] 表示原树中以 u 为根的子树的大小。注意上面的都是不包含 a, b 两个点的，还需要把没被统计的点加上，这个东西不难处理，读者不妨想一想。
还有这题输出格式是行末带空格的。。。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 300010
#define maxm 600010
#define maxlog 20
#define oo 2147483647
int n, m, head[maxn], next[maxm], to[maxm];
void AddEdge(int a, int b) {
to[++m] = b; next[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; next[m] = head[a]; head[a] = m;
return ;
}
int ord[maxn], clo, dep[maxn], fa[maxlog][maxn], siz[maxn];
void build(int u) {
ord[u] = ++clo; siz[u] = 1;
for(int i = 1; i < maxlog; i++) fa[i][u] = fa[i-1][fa[i-1][u]];
for(int e = head[u]; e; e = next[e]) if(to[e] != fa[0][u]) {
dep[to[e]] = dep[u] + 1;
fa[0][to[e]] = u;
build(to[e]);
siz[u] += siz[to[e]];
}
return ;
}
int lca(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
for(int i = maxlog - 1; i >= 0; i--) if(dep[a] - (1 << i) >= dep[b]) a = fa[i][a];
for(int i = maxlog - 1; i >= 0; i--) if(fa[i][a] != fa[i][b]) a = fa[i][a], b = fa[i][b];
return a == b ? a : fa[0][b];
}
bool cmp(int a, int b) { return ord[a] < ord[b]; }
int cpi, Ps[maxn], psi[maxn], cp, ps[maxn], vis[maxn];
bool flg[maxn];
int M, Head[maxn], Next[maxm], To[maxm], Dist[maxm];
void Add2(int a, int b, int c) {
// printf("%d -- %d : %d
", a, b, c);
To[++M] = b; Dist[M] = c; Next[M] = Head[a]; Head[a] = M;
swap(a, b);
To[++M] = b; Dist[M] = c; Next[M] = Head[a]; Head[a] = M;
return ;
}
int f[maxn], id[maxn], ans[maxn];
void dp1(int u, int pa) {
// printf("u: %d
", u);
f[u] = id[u] = oo;
if(flg[u]) f[u] = 0, id[u] = u; flg[u] = 0;
for(int e = Head[u]; e; e = Next[e]) if(To[e] != pa) {
dp1(To[e], u);
int tmp = f[To[e]] + Dist[e];
if(tmp < f[u]) f[u] = tmp, id[u] = id[To[e]];
else if(tmp == f[u] && id[To[e]] < id[u]) id[u] = id[To[e]];
}
return ;
}
void dp2(int u, int pa) {
for(int e = Head[u]; e; e = Next[e]) if(To[e] != pa) {
int tmp = f[u] + Dist[e];
if(tmp < f[To[e]]) f[To[e]] = tmp, id[To[e]] = id[u];
else if(tmp == f[To[e]] && id[u] < id[To[e]]) id[To[e]] = id[u];
dp2(To[e], u);
}
// printf("f[%d] = %d, id[%d] = %d
", u, f[u], u, id[u]);
return ;
}
int jump(int u, int d) {
for(int i = maxlog - 1; i >= 0; i--) if(d >= (1 << i))
d -= (1 << i), u = fa[i][u];
return u;
}
void process(int u, int pa) {
int S = siz[u];
for(int e = Head[u]; e; e = Next[e]) if(To[e] != pa) {
int tmp = f[u] - f[To[e]] + Dist[e] >> 1;
if(f[u] - f[To[e]] + Dist[e] & 1) ; else tmp -= id[u] < id[To[e]];
int mid = jump(To[e], tmp), son = jump(To[e], Dist[e] - 1);
// printf("processing: (%d %d) mid(%d) son(%d)
", u, To[e], mid, son);
ans[id[u]] += siz[son] - siz[mid];
ans[id[To[e]]] += siz[mid] - siz[To[e]];
S -= siz[son];
process(To[e], u);
}
ans[id[u]] += S;
Head[u] = 0;
return ;
}
int main() {
n = read();
for(int i = 1; i < n; i++) {
int a = read(), b = read();
AddEdge(a, b);
}
build(1);
// for(int i = 1; i <= n; i++) printf("%d%c", ord[i], i < n ? ' ' : '
');
int q = read();
while(q--) {
cpi = read(); cp = 0;
for(int i = 1; i <= cpi; i++) {
Ps[i] = psi[i] = read();
ps[++cp] = psi[i];
flg[ps[cp]] = 1;
vis[ps[cp]] = q + 1;
}
sort(psi + 1, psi + cpi + 1, cmp);
for(int i = 1; i < cpi; i++) {
int c = lca(psi[i], psi[i+1]);
if(vis[c] != q + 1) ps[++cp] = c, vis[c] = q + 1;
}
sort(ps + 1, ps + cp + 1, cmp);
int rt = ps[1], dr = dep[rt];
M = 0;
for(int i = 1; i < cp; i++) {
int a = ps[i], b = ps[i+1], c = lca(a, b);
Add2(b, c, dep[b] - dep[c]);
if(dep[c] < dr) dr = dep[c], rt = c;
}
int tmp = siz[rt];
if(rt != 1) siz[rt] = n;
dp1(rt, 0);
dp2(rt, 0);
for(int i = 1; i <= cpi; i++) ans[psi[i]] = 0;
process(rt, 0);
siz[rt] = tmp;
if(cpi > 1){ for(int i = 1; i <= cpi; i++) printf("%d ", ans[Ps[i]]); putchar('
'); }
else printf("%d
", n);
}
return 0;
}