https://www.luogu.org/problemnew/show/P1600

https://www.zybuluo.com/wsndy-xx/note/1135243

乱写的暴力，这道题暴力写个60还是比较简单的

#include
#include
#include
#include
#include

using namespace std;
const int N = ;
const int oo = ;

#define lson jd << 1
#define rson jd << 1 | 1

#define yxy getchar()
#define one_ n <= 993
#define two_ n == 99994
#define three_ n == 99995

int head[N], pre[N], dis[N], tim[N], Answer[N], Askl[N], Askr[N];
bool vis[N];
int n, m, now = ;
struct Node {
int u, v, w, nxt;
} G[N];
queue Q;
vector Vt[N];
int L[N << ], R[N << ], W[N << ], F[N << ];

inline int read() {
int x = ;
char c = yxy;
while(c < '' || c > '') c = yxy;
while(c >= '' && c <= '') x = x * + c - '', c = yxy;
return x;
}

inline void add(int u, int v) {
G[now].v = v;
G[now].nxt = head[u];
head[u] = now ++;
}

inline void spfa(int start,int endd) {
for(int i = ; i <= n; i ++) dis[i] = oo, vis[i] = ; dis[start] = ; Q.push(start); while(!Q.empty()) { int topp = Q.front(); Q.pop(); vis[topp] = ; for(int i = head[topp]; ~ i; i = G[i].nxt) { if(dis[G[i].v] > dis[topp] + ) {
dis[G[i].v] = dis[topp] + ;
pre[G[i].v] = topp;
if(!vis[G[i].v]) {
vis[G[i].v] = ;
Q.push(G[i].v);
}
}
}
}
}

void calc(int start, int endd, int diss) {
int js = -;
pre[start] = ;
while(endd) {
js ++;
if(tim[endd] == diss - js) Answer[endd] ++;
endd = pre[endd];
}
}

void work_1() {
for(int i = ; i <= m; i ++) {
spfa(Askl[i], Askr[i]);
calc(Askl[i], Askr[i], dis[Askr[i]]);
}
}

void work_2() {
for(int i = ; i <= m; i ++) Vt[Askl[i]].push_back(Askr[i]); for(int i = ; i <= n; i ++) { int L_ = i - tim[i], R_ = i + tim[i]; int siz_ = Vt[L_].size(); if(L_ > )
for(int j = ; j < siz_; j ++) if(Vt[L_][j] >= i) Answer[i] ++;
siz_ = Vt[R_].size();
if(R_ <= n)
for(int j = ; j < siz_; j ++)
if(Vt[R_][j] <= i) Answer[i] ++;
}
}

int bef[N], top[N], deep[N], size[N], fa[N], son[N], tree[N], spjs;
int cnt[N];

void Dfs_3(int u, int f_, int dep) {
fa[u] = f_, deep[u] = dep; size[u] = ;
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(v != f_) {
dis[v] = dis[u] + ;
Dfs_3(v, u, dep + );
size[u] += size[v];
cnt[u] += cnt[v];
}
}
}

inline void work_3() {
memset(dis, , sizeof dis);
for(int i = ; i <= m; i ++) cnt[Askr[i]] ++;
Dfs_3(, , );
for(int i = ; i <= n; i ++)
if(deep[i] == tim[i])
Answer[i] += cnt[i];
}

int main() {
n = read();
m = read();
for(int i = ; i <= n; i ++) head[i] = -;
for(int i = ; i <= n - ; i ++) {
int u = read();
int v = read();
add(u, v);
add(v, u);
}
for(int i = ; i <= n; i ++) tim[i] = read();
for(int i = ; i <= m; i ++) Askl[i] = read(), Askr[i] = read();
if(one_) work_1();
else if(two_) work_2();
else if(three_) work_3(); //起点 == 1
for(int i = ; i <= n; i ++) printf("%d ", Answer[i]);
return ;
}

前置知识

Lca + 线段树 + 差分 + 树剖

考虑把一条路径拆成两段（这是非常常见的解决树上问题的方法）

分别拆成 S - L 和 L - T （起点 -  Lca， Lca  -  终点）

这样就可以得到当满足

deep[s] - deep[i] = wat[i]  =>  deep[s] = wat[i] + deep[i];

deep[s] + deep[i] - 2 * deep[Lca(s, i)] = wat[i]  =>  deep[s] - 2 * deep[Lca(s, i)] = wat[i] - deep[i];

时玩家才会被 i 观察员看到

发现 上面两个式子满足等式右边都是定值

因此我们可以 以深度建立线段树(动态开节点)

查询时就应该查询该节点所对应的深度的线段树的区间lst[] 和 rst[] 之间的总的权值

lst[i] 表示以该节点为子树的根中树上编号的下界, 同理rst[]为上界(涉及到DFS序 && 树剖的知识).

#include
#include
#include

using namespace std;
const int N = 3e5 + ;

#define gc getchar()

int n, m, wat[N];
int Askl[N], Askr[N], Lca[N];

int now = , head[N];
struct Node {int v, nxt;} G[N << ];

inline int read() {
int x = ; char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c <= '') x = x * + c - '', c = gc;
return x;
}

inline void Add(int u, int v) {G[now].v = v; G[now].nxt = head[u]; head[u] = now ++;}

int fa[N], deep[N], top[N], size[N], son[N], lst[N], rst[N], tree[N], Spjs;

void Dfs_1(int u, int f_, int dep) {
fa[u] = f_; deep[u] = dep; size[u] = ;
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(v != f_) {
Dfs_1(v, u, dep + );
size[u] += size[v];
if(size[son[u]] < size[v]) son[u] = v;
}
}
}

void Dfs_2(int u, int tp) {
top[u] = tp;
lst[u] = ++ Spjs;
tree[u] = Spjs;
if(! son[u]) {rst[u] = Spjs; return ;}
Dfs_2(son[u], tp);
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(v != fa[u] && v != son[u]) Dfs_2(v, v);
}
rst[u] = Spjs;
}

inline int Ask_Lca(int x, int y) {
int tp1 = top[x], tp2 = top[y];
while(tp1 != tp2) {
if(deep[tp1] < deep[tp2]) swap(x, y), swap(tp1, tp2);
x = fa[tp1];
tp1 = top[x];
}
return deep[x] < deep[y] ? x : y;
}

int root[N * ], lson[N * ], rson[N * ], W[N * ], tot, cnt;

void Build_G(int l, int r, int & jd, int x, int yj) {
if(!x) return ;
if(!jd) jd = ++ tot;
W[jd] += yj;
if(l == r) return ;
int mid = (l + r) >> ;
if(x <= mid) Build_G(l, mid, lson[jd], x, yj);
else Build_G(mid + , r, rson[jd], x, yj);
}

int Sec_A(int jd, int l, int r, int x, int y) {
if(! jd) return ;
if(x <= l && r <= y) return W[jd]; int mid = (l + r) >> ;
if(y <= mid) return Sec_A(lson[jd], l, mid, x, y); else if(x > mid) return Sec_A(rson[jd], mid + , r, x, y);
else return Sec_A(lson[jd], l, mid, x, y) + Sec_A(rson[jd], mid + , r, x, y);
}

void Clear() {
tot = ;
memset(lson, , sizeof lson);
memset(rson, , sizeof rson);
memset(W, , sizeof W);
memset(root, , sizeof root);
}

int Answer[N];

int main() {
n = read(); m = read();
for(int i = ; i <= n; i ++) head[i] = -;
for(int i = ; i <= n - ; i ++) {
int u = read(), v = read();
Add(u, v); Add(v, u);
}
for(int i = ; i <= n; i ++) wat[i] = read();
for(int i = ; i <= m; i ++) Askl[i] = read(), Askr[i] = read();
Dfs_1(, , );
Dfs_2(, );
for(int i = ; i <= m; i ++) Lca[i] = Ask_Lca(Askl[i], Askr[i]);
int dep;
for(int i = ; i <= m; i ++) {
dep = deep[Askl[i]];
Build_G(, n, root[dep], tree[Askl[i]], );
Build_G(, n, root[dep], tree[fa[Lca[i]]], -);
}
for(int i = ; i <= n; i ++)
Answer[i] = Sec_A(root[deep[i] + wat[i]], , n, lst[i], rst[i]);
Clear();
for(int i = ; i <= m; i ++) {
dep = deep[Askl[i]] - deep[Lca[i]] * + n * ;
Build_G(, n, root[dep], tree[Askr[i]], );
Build_G(, n, root[dep], tree[Lca[i]], -);
}
for(int i = ; i <= n; i ++)
Answer[i] += Sec_A(root[wat[i] - deep[i] + n * ], , n, lst[i], rst[i]);
for(int i = ; i <= n; i ++)
cout << Answer[i] << " ";
return ;
}