今天寫了一道題目，需要采用線段樹合并+樹上差分來解決

題目鏈接：P1600 [NOIP2016 提高組] 天天愛跑步 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

其實當時已經想到要用這兩種方法，但苦于一直找不到轉移方程，最后看了答案才領悟到一點推導公式的思路

我一開始的想法是對于起點s和終點t而言，對于x到其lca的路徑中的節點，有人出現的時間結點就是dep[x]一直往上遞推過去，然后我只需要最后合并找出符合w[i]的時間點就行了

但細想一下這個方法根本就不能實現，首先是lca到t的路徑的結點無法處理，其次是差分數組加和的時候每次區間下標都要+1，而且也不知道x出發的人到哪個結點就消失，所以這種順推的遞推公式并不成立

那正確的思路是什么呢？

對于x到y路徑

我們先分析x到lca的路徑上的結點i，對于這個節點i，如果x出發的人能夠被他觀測到，那么應該滿足關系式：dep[x]-dep[i]=w[i]，這樣一來，我們就可以得到：dep[i]+w[i]=dep[x]，也就是說，對于路徑上的每個這樣的結點i，我們只要計數dep[x]的個數，就可以知道他能夠觀測到多少個人了

我們再來分析lca到y的路徑上的結點j，對于這個結點j，如果x出發的人能夠被他觀測到，那么應該滿足關系式：dep[x]-dep[lca]+dep[j]-dep[lca]=w[j]，這樣一來，我們就可以得到：dep[j]-w[i]=2*dep[lca]-dep[x]，也就是說，對于路徑上的每個這樣的結點j，我們只需要計數2*dep[lca]-dep[x]的個數，就可以知道他可以觀測到多少個人了

那么我們需要從哪里開始修改呢？

顯然這些dep[x],2*dep[lca]-dep[x]所代表的人的個數只在x到y這條路徑上生效，也就是說，我們只需要修改x結點上dep[x]的個數，然后在由下往上合并差分數組的時候，每個在路徑(x,lca)的結點都可以享受到這份dep[x]的貢獻。同理，我們只需要修改y結點上2*dep[lca]-dep[x]的個數，那么每個在路徑(lca,y)的節點都可以享受到這份2*dep[lca]-dep[x]的貢獻

而對于他們的lca來說，它既享受到了dep[x]的貢獻，又享受到了2*dep[lca]-dep[x]的貢獻，哪份是它不應該擁有的呢？其實這兩者在這個節點這里是等效的，所以我們隨機減免一個就可以了，我們這里選擇給dep[x]的權值減1。那么對于lca的父親而言，它就多享受到了一個2*dep[lca]-dep[x]的貢獻，因此我們給其2*dep[lca]-dep[x]的權值-1，從而把這個差分修改的影響限制在了路徑(x,y)中

這里我們選擇用線段樹來維護這個權值區間

實現代碼如下:

數組版本：

//樹上差分來處理樹上路徑的信息
//每個點建一棵權值線段樹
//結點深度為區間下標
//sum維護結點深度出現的次數#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 3E5 + 10, M = N << 1;
#define mid (l+r>>1)
//鏈式前向星
int to[M], nxt[M], h[N], idx;
//左兒子，右兒子，sum差分權值和
int ls[N * 100], rs[N * 100], sum[N * 100];
//fa倍增父親
//dep節點深度
int fa[N][22], dep[N];
//n棵線段樹
int root[N], tot;
int lg[N];
//w：觀察員
//ans：第i個節點的答案
int n, m, w[N], ans[N];
//加邊
void add(int a,int b){to[++idx] = b;nxt[idx] = h[a];h[a] = idx;
}
//lg[i]==log2+1,i向下取整
void init(){for (int i = 1; i <= n;i++){lg[i] = lg[i - 1] + (1<<lg[i-1] == i);}
}
//快讀
void read(int &x){x = 0;char c = getchar();while(!isdigit(c)){c = getchar();}while(isdigit(c)){x = (x << 3 + x << 1) + c - '0';c = getchar();}
}//樹增
void dfs(int x,int f){dep[x] = dep[f] + 1;fa[x][0] = f;//距離x的遞增父親的距離不會超過x的深度for (int i = 1; i < lg[dep[x]];i++){//距離x的距離為2^i的父親等于距離x的距離為2^(i-1)的父親的距離它為距離2^(i-1)的父親fa[x][i] = fa[fa[x][i - 1]][i - 1];}//遞歸每一個子結點for (int i = h[x], y; y = to[i];i=nxt[i]){if(y!=f)dfs(y, x);}
}int lca(int x,int y){//默認x為深度大的結點if(dep[x]<dep[y]){swap(x, y);}//往上爬的距離不會超過x與y的深度差for (int i = lg[dep[x] - dep[y]] - 1; ~i;i--){//如果跳到父親的深度還是比y大，可以放心跳if(dep[fa[x][i]]>=dep[y]){x = fa[x][i];}}if(x==y){return y;}for (int i = lg[dep[x]] - 1; ~i;i--){if(fa[x][i]!=fa[y][i]){x = fa[x][i];y = fa[y][i];}}return fa[x][0];
}//動態開點
//單點修改
void change(int &u,int l,int r,int p,int k){if(!u)u = ++tot;if(l==r){sum[u] += k;return;}if(p<=mid){change(ls[u], l, mid, p, k);}else{change(rs[u], mid + 1, r, p, k);}
}//把x線段樹合并到y上
int merge(int x,int y,int l,int r){if(!x||!y){return x + y;}if(l==r){sum[x] += sum[y];return x;}ls[x] = merge(ls[x], ls[y], l, mid);rs[x] = merge(rs[x], rs[y], mid + 1, r);return x;
}//單點查詢
int query(int u,int l,int r,int p){if(l==r){return sum[u];}if(p<=mid){return query(ls[u], l, mid, p);}else{return query(rs[u], mid + 1, r, p);}
}//遞歸合并線段樹
void dfs2(int x){for (int i = h[x], y; y = to[i];i=nxt[i]){if(y==fa[x][0])continue;dfs2(y);//由于整體向右平移了值域n，所以線段樹的區間要開到2*nroot[x]=merge(root[x],root[y],1,n<<1);}//如果這里有觀察員//而且if(w[x]&&n+dep[x]+w[x]<=(n<<1)){ans[x] += query(root[x], 1, n << 1, n + dep[x] + w[x]);}ans[x] += query(root[x], 1, n << 1, n + dep[x] - w[x]);
}int main(){scanf("%d%d", &n, &m);for (int i = 1, x, y; i < n;i++){scanf("%d%d", &x, &y);add(x, y);add(y, x);}init();for (int i = 1; i <= n;i++){scanf("%d", w + i);}dfs(1, 0);for (int i = 1, x, y,l; i <= m;i++){scanf("%d%d", &x, &y);l = lca(x, y);change(root[x], 1, n << 1, n + dep[x], 1);change(root[y], 1, n << 1, n + 2 * dep[l] - dep[x], 1);change(root[l], 1, n << 1, n + dep[x], -1);change(root[fa[l][0]], 1, n << 1, n + 2 * dep[l] - dep[x],-1);}dfs2(1);for (int i = 1; i <= n;i++){printf("%d ",ans[i]);}return 0;
}

指針版本：

#include <iostream>
#include <cstdio>
#include <cstring>
#define mid (l+r>>1)
using namespace std;
struct tree {struct tree* l = nullptr, * r = nullptr;int sum=0;
};
const int N = 3E5 + 10, M = N << 1;
int to[M], nxt[M], h[N], tot;
void add(int a, int b) {to[++tot] = b;nxt[tot] = h[a];h[a] = tot;
}
tree* tr[N];
int son[N], siz[N], top[N], dep[N], fa[N];
int ans[N], w[N];
int n, m;
//fa,dep,siz,son
void dfs1(int u) {dep[u] = dep[fa[u]] + 1;siz[u] = 1;for (int i = h[u], v; v = to[i]; i = nxt[i]) {if (v == fa[u])continue;fa[v] = u;dfs1(v);siz[u] += siz[v];if (siz[v] > siz[son[u]])son[u] = v;}
}//top
void dfs2(int u, int tp) {top[u] = tp;top[son[u]] = tp;if(son[u])dfs2(son[u], tp);for (int i = h[u], v; v = to[i]; i = nxt[i]) {if (v == fa[u] || v == son[u])continue;dfs2(v, v);}
}//公共祖先
int lca(int x, int y) {//不在一條鏈上的時候while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) {swap(x, y);}x = fa[top[x]];}return dep[x] < dep[y] ? x : y;
}//點修
void change(tree** u, int l, int r, int p, int k) {if (!*u) {*u = new tree;}if (l == r) {(*u)->sum += k;return;}if (p <= mid) {change(&((*u)->l), l, mid, p, k);}else {change(&((*u)->r), mid + 1, r, p, k);}//反正不用區間查找，所以不Pushup也沒關系了
}//點查
int query(tree* u, int l, int r, int p) {if (!u) {return 0;}if (l == r) {return u->sum;}if (p <= mid) {return query(u->l, l, mid, p);}else {return query(u->r, mid + 1, r, p);}
}tree* merge(tree* x, tree* y) {if (!x || !y) {return x ? x : y;}x->sum += y->sum;x->l = merge(x->l, y->l);x->r = merge(x->r, y->r);return x;
}void dfs3(int u) {for (int i = h[u], v; v = to[i]; i = nxt[i]) {if (v == fa[u])continue;dfs3(v);tr[u] = merge(tr[u], tr[v]);}if (w[u]&&dep[u] + w[u] <= n) {ans[u] += query(tr[u], -n, n, dep[u] + w[u]);}ans[u] += query(tr[u], -n, n, dep[u] - w[u]);
}int main() {scanf("%d%d", &n, &m);for (int i = 1, x, y; i < n; i++) {scanf("%d%d", &x, &y);add(x, y);add(y, x);}for (int i = 1; i <= n; i++) {scanf("%d", w + i);}dfs1(1);dfs2(1, 1);for (int i = 1, s, t, l; i <= m; i++) {scanf("%d%d", &s, &t);l = lca(s, t);change(&tr[s], -n, n, dep[s], 1);change(&tr[t], -n, n, 2 * dep[l] - dep[s], 1);change(&tr[l], -n, n, dep[s], -1);change(&tr[fa[l]], -n, n, 2 * dep[l] - dep[s], -1);}dfs3(1);for (int i = 1; i <= n; i++) {printf("%d ", ans[i]);}return 0;
}