初見安~本專題/題解 是有前置知識的哦：LCA
樹上差分——顧名思義就是把差分運用到樹上。【啪！
本來差分是相鄰作差，可以用于求數軸上被線段覆寫的最大層數。求解時可以線上段的左短點和右端點+1處标記+1和-1。
樹上差分也是同樣的道理，我們可以先看一個例題來講解：
傳送門：洛谷P3128
題目描述
Farmer John has installed a new system of N-1N−1 pipes to transport milk between the NN stalls in his barn (2 \leq N \leq 50,0002≤N≤50,000), conveniently numbered 1 \ldots N1…N. Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.
FJ is pumping milk between KK pairs of stalls (1 \leq K \leq 100,0001≤K≤100,000). For the iith such pair, you are told two stalls s_isi and t_iti, endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the KK paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from s_isito t_iti, then it counts as being pumped through the endpoint stalls s_isi and
t_iti, as well as through every stall along the path between them.
FJ給他的牛棚的N(2≤N≤50,000)個隔間之間安裝了N-1根管道，隔間編号從1到N。所有隔間都被管道連通了。
FJ有K(1≤K≤100,000)條運輸牛奶的路線，第i條路線從隔間si運輸到隔間ti。一條運輸路線會給它的兩個端點處的隔間以及中間途徑的所有隔間帶來一個機關的運輸壓力，你需要計算壓力最大的隔間的壓力是多少。
輸入格式：
The first line of the input contains NN and KK.
The next N-1N−1 lines each contain two integers xx and yy (x \ne yx≠y) describing a pipe
between stalls xx and yy.
The next KK lines each contain two integers ss and tt describing the endpoint
stalls of a path through which milk is being pumped.
輸出格式：
An integer specifying the maximum amount of milk pumped through any stall in the
barn.
輸入樣例#1：
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
輸出樣例#1：
9
題解：
這就是一個樹上差分的裸題，題意我們可以看出其實和線段上的差分是類似的。
這個題我們可以同樣用+1和-1來考慮——假設目前的運輸路徑是從u->v
那麼這條路徑上的點權都要+1。一般樹上的操作都是要dfs到底然後回溯操作的，是以結合查分的思想，我們可以設一個查分數組tot，然後tot[ u ]++,tot[ v ]++；這樣一來就表示自下而上從u、從v開始多了一層覆寫；很明顯在兩點的lca處重複覆寫了一層，是以要tot[ lca ]--；當然這層覆寫是要去掉的，我們還要在tot[ fa[ lca ] ] --。也就是：
然後這個問題就解決完了！！！最後dfs掃一遍得出最大的tot就行了。
下面上代碼——
#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
int n, m;
int read()
{
int x = 0, ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x;
}
vector<int> t[maxn];
int ans = 0, tot[maxn];
int fa[maxn], dep[maxn], size[maxn], top[maxn], son[maxn];
struct hld//這裡選擇了用樹剖求LCA，就打個包了
{
void dfs1(int u)
{
register int v;
size[u] = 1;
for(int i = 0; i < t[u].size(); i++)
{
v = t[u][i]; if(v == fa[u]) continue;
dep[v] = dep[u] + 1, fa[v] = u;
dfs1(v);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp)
{
register int v;
top[u] = tp;
if(son[u]) dfs2(son[u], tp);
for(int i = 0; i < t[u].size(); i++)
{
v = t[u][i];
if(v != fa[u] && v != son[u]) dfs2(v, v);
}
}
int ask(int u, int v)
{
while(top[u] != top[v])
{
if(dep[top[u]] > dep[top[v]]) swap(u, v);
v = fa[top[v]];
}
return dep[u] > dep[v]? v : u;
}
}HLD;
void dfs(int u)//最後掃一遍得出答案
{
register int v;
for(int i = 0; i < t[u].size(); i++)
{
v = t[u][i];
if(v == fa[u]) continue;
dfs(v);
tot[u] += tot[v];
}
ans = max(ans, tot[u]);
// printf("tot:%d %d\n", u, tot[u]);
}
int main()
{
memset(tot, 0, sizeof tot);
n = read(), m = read();
register int u, v, lca;
for(int i = 1; i < n; i++)
u = read(), v = read(), t[u].push_back(v), t[v].push_back(u);
HLD.dfs1(1), HLD.dfs2(1, 1);//樹剖初始化
for(int i = 1; i <= m; i++)
{
u = read(), v = read();
tot[u]++, tot[v]++;//标記
lca = HLD.ask(u, v);
tot[lca]--, tot[fa[lca]]--;//标記
if(lca == 1) tot[1]--;//特殊處理，因為在0點操作沒有意義
}
dfs(1);
printf("%d\n", ans);
return 0;
}
思路還是很簡單的，樹上差分也是很巧妙的。
還有個水題就是松鼠的新家【傳送門：洛谷P3258
題目描述
松鼠的新家是一棵樹，前幾天剛剛裝修了新家，新家有n個房間，并且有n-1根樹枝連接配接，每個房間都可以互相到達，且倆個房間之間的路線都是唯一的。天哪，他居然真的住在”樹“上。
松鼠想邀請小熊維尼前來參觀，并且還指定一份參觀指南，他希望維尼能夠按照他的指南順序，先去a1，再去a2，......，最後到an，去參觀新家。可是這樣會導緻維尼重複走很多房間，懶惰的維尼不停地推辭。可是松鼠告訴他，每走到一個房間，他就可以從房間拿一塊糖果吃。
維尼是個饞家夥，立馬就答應了。現在松鼠希望知道為了保證維尼有糖果吃，他需要在每一個房間各放至少多少個糖果。
因為松鼠參觀指南上的最後一個房間an是餐廳，餐廳裡他準備了豐盛的大餐，是以當維尼在參觀的最後到達餐廳時就不需要再拿糖果吃了。
輸入格式：
第一行一個整數n，表示房間個數第二行n個整數，依次描述a1-an
接下來n-1行，每行兩個整數x，y，表示标号x和y的兩個房間之間有樹枝相連。
輸出格式：
一共n行，第i行輸出标号為i的房間至少需要放多少個糖果，才能讓維尼有糖果吃。
輸入樣例#1：
5
1 4 5 3 2
1 2
2 4
2 3
4 5
輸出樣例#1：
1
2
1
2
1
說明：
2<= n <=300000
題解：
這個題也是一個樹上差分的裸題——不管其他的限制條件，翻譯過來就是求每個點被路徑覆寫的層數。是以操作和前一個題幾乎一模一樣！！！求LCA然後n - 1個線段差分覆寫就行了。
是以現在我們來處理細節問題——因為我們從第二次觀光【a2~a3】開始，每個起點都是在作為終點的時候計算過一次的，是以答案都要-1；至于an是餐廳，我們就直接2~n都-1就可以了。第一個點也是要放糖的，就不動了。
我最後是卡在了一個很愚蠢的細節——不一定是從1号房間開始啊！！！沒有減的那個房間不應該是1号，而是a1号！！！
好了，上代碼了：）
#include<bits/stdc++.h>
#define maxn 300005
using namespace std;
int n;
int read()
{
int x = 0, ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x;
}
vector<int> t[maxn];//同樣的，關注的是點權，是以可以直接用vector
int a[maxn], tot[maxn];
int dep[maxn], son[maxn], size[maxn], top[maxn], fa[maxn];
struct hld//老樣子，樹剖求LCA
{
void dfs1(int u)
{
register int v;
size[u] = 1;
for(int i = 0; i < t[u].size(); i++)
{
v = t[u][i]; if(v == fa[u]) continue;
fa[v] = u; dep[v] = dep[u] + 1;
dfs1(v);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp)
{
register int v;
top[u] = tp;
if(son[u]) dfs2(son[u], tp);
for(int i = 0; i < t[u].size(); i++)
{
v = t[u][i];
if(v != fa[u] && v != son[u]) dfs2(v, v);
}
}
int ask(int u, int v)
{
while(top[u] != top[v])
{
if(dep[top[u]] > dep[top[v]]) swap(u, v);
v = fa[top[v]];
}
return dep[u] > dep[v]? v : u;
}
}HLD;
void dfs(int u)
{
register int v;
for(int i = 0; i < t[u].size(); i++)
{
v = t[u][i];
if(v == fa[u]) continue;
dfs(v);
tot[u] += tot[v];//直接累加就可以了
}
}
int main()
{
n = read();
register int u, v;
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i < n; i++)
u = read(), v = read(), t[u].push_back(v), t[v].push_back(u);
HLD.dfs1(1); HLD.dfs2(1, 1);
for(int i = 1; i < n; i++)
{
tot[a[i]]++, tot[a[i + 1]]++;
register int lca = HLD.ask(a[i], a[i + 1]);
tot[lca]--; tot[fa[lca]]--;//樹上差分基礎操作
}
dfs(1);
tot[a[1]]++;//提前+1是為了讓-1的操作對它沒有影響
for(int i = 1; i <= n; i++)
printf("%d\n", tot[i] - 1);
return 0;
}
最後還有一個毒瘤題，可以在多練幾個難度大一些的題【傳送門建設中】後刷一下：天天愛跑步
迎評：）
——End——