分析：这道题真心烦啊，是我做过noip真题中难度最高的一道了，到今天为止才把noip2016的坑给填满.暴力的话前60分应该是可以拿满的，后40分还是很有难度的.
定义：每个人的起点、终点：s,t;深度:deep[i];观察员出现时间：w[i];
首先，树上两个点的最短路径肯定要经过LCA,那么对于路径x ---> y我们可以分成两部分：1.x ---> lca. 2.lca ---> y.先分析第一段路上的观察员i,显然s到i的距离等于w[i]才行，这段路是从x向上跳的，所以可以得到式子：
deep[s] - deep[i] = w[i].
移项，得到：
deep[s] = deep[i] + w[i].
可以发现右边是固定的，那么我们只需要找出以i为根的子树中深度为deep[i] + w[i]的点中，有多少起点.对于子树的修改查询，我们通常转换为区间来做，方法是dfs序+线段树。只是这个线段树的姿势有点特别：动态加点，每一个深度建一棵线段树。
现在我们把第一段路简化为区间[a,b],当有一个人的起点满足条件时，我们要使[a,b] + 1,具体怎么实现呢？可以参考noip2012借教室，利用差分思想,在s[a]处+1,在s[b + 1]处-1，这个操作是在线段树上完成的,这样就避免了区间修改，而变成了单点修改,主要是为了避免使用lazy标记.为什么要-1呢？我们可以这么理解：我要查询i的子树，如果i不在第一段路上，我如果不-1，那么就会统计进入答案.
操作完后，每次查询深度为deep[i] + w[i]的深度的点中有多少起点就好了.
下面分析第二段路，其实操作类似，不过就是式子变了：
deep[s] + deep[i] - 2*deep[lca(s,i)] = w[i].
这个式子也是比较显然的，在图上推一下就可以得到，移项也可以得到：
deep[s] - 2*deep[lca(s,i)] = w[i] - deep[i]
然后的处理方法就和上面是一样的，不过要注意，式子左边可能会等于负数，那么我们将下标都向右移2*n位就可以了.
参考：传送门，这位神犇用的方法是树链剖分求lca,不过我的是用的倍增，其实都差不多啦.
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<cmath> #include<map> using namespace std; const int inf = 0x7ffffff; int n, m, tot = 1, head[300010], to[600010], nextt[600010], w[300010], dfs_clock, in[300010], out[300010], deep[300010], fa[300010][21], id[300010]; int root[300010 * 3], lc[300010 * 25], rc[300010 * 25], ans[300010], cnt, sum[300010 * 25]; struct node { int s, t, lca; }e[300010]; void add(int x, int y) { to[tot] = y; nextt[tot] = head[x]; head[x] = tot++; } void dfs(int u, int d, int from) { in[u] = ++dfs_clock; id[u] = dfs_clock; deep[u] = d; for (int i = head[u]; i; i = nextt[i]) { int v = to[i]; if (v != from) { dfs(v, d + 1, u); fa[v][0] = u; } } out[u] = dfs_clock; } int getlca(int x, int y) { if (x == y) return x; if (deep[x] < deep[y]) swap(x, y); for (int j = 19; j >= 0; j--) if (deep[fa[x][j]] >= deep[y]) x = fa[x][j]; if (x == y) return x; for (int j = 19; j >= 0; j--) if (fa[x][j] != fa[y][j]) { x = fa[x][j]; y = fa[y][j]; } return fa[x][0]; } void init() { cnt = 0; memset(lc, 0, sizeof(lc)); memset(rc, 0, sizeof(rc)); memset(sum, 0, sizeof(sum)); memset(root, 0, sizeof(root)); } void update(int &o, int l, int r, int p, int v) { if (!p) return; if (!o) o = ++cnt; sum[o] += v; if (l == r) return; int mid = (l + r) >> 1; if (p <= mid) update(lc[o], l, mid, p, v); else update(rc[o], mid + 1, r, p, v); } int query(int o, int l, int r, int x, int y) { if (!o) return 0; if (x <= l && r <= y) return sum[o]; int mid = (l + r) >> 1, res = 0; if (x <= mid) res += query(lc[o], l, mid, x, y); if (y > mid) res += query(rc[o], mid + 1, r, x, y); return res; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); add(u, v); add(v, u); } for (int i = 1; i <= n; i++) scanf("%d", &w[i]); for (int i = 1; i <= m; i++) scanf("%d%d", &e[i].s, &e[i].t); dfs(1, 1, 0); //预处理出dfs序和深度和fa数组 /* for (int i = 1; i <= n; i++) printf("%d %d %d ", i, in[i], out[i]); */ for (int j = 1; j <= 19; j++) for (int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1]; for (int i = 1; i <= m; i++) e[i].lca = getlca(e[i].s, e[i].t); for (int i = 1; i <= m; i++) { int tt = deep[e[i].s]; update(root[tt], 1, n, id[e[i].s], 1); update(root[tt], 1, n, id[fa[e[i].lca][0]], -1); } for (int i = 1; i <= n; i++) ans[i] = query(root[deep[i] + w[i]], 1, n, in[i], out[i]); init(); //第一次线段树后一定要清空 for (int i = 1; i <= m; i++) { int tt = deep[e[i].s] - deep[e[i].lca] * 2 + n * 2; update(root[tt], 1, n, id[e[i].t], 1); update(root[tt], 1, n, id[e[i].lca], -1); //关于这里为什么不用fa[lca][0],目的是为了避免重复计算lca的贡献. } for (int i = 1; i <= n; i++) ans[i] += query(root[w[i] - deep[i] + n * 2], 1, n, in[i], out[i]); for (int i = 1; i <= n; i++) printf("%d ", ans[i]); return 0; }