1. LCA(求最近公共父节点 ， 求树上两点最短距离)

先求节点深度 ， 处理 fa 数组 ， 然后做LCA过程

板子(有根树 ， 无根树默认 1 为根即可)

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 1e6+10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;vector<int>ve[N];
int n , m , s , d[N] , f[N][21]; // 第 i 个点的前 (1 << j) 个祖先是谁void dfs(int x,int fa){f[x][0] = fa;for(int i=1;(1<<i)<=d[x];i++) f[x][i] = f[f[x][i-1]][i-1];//更新 st 表/*注意这里一定要写 小于等于(<=) 避免粗心导致忘记初始化 d[root] = 1写小于等于两种情况都合适*/for(auto k : ve[x]){if(k == fa) continue;d[k] = d[x] + 1;dfs(k,x);}//更新深度
}int lca(int x,int y){if(d[x] < d[y]) swap(x , y);//d[x] 深度大for(int i=20;i>=0;i--) if(d[x] - (1 << i) >= d[y])	x = f[x][i];//跳到相同位置if(x == y) return x;//到达同一个点for(int i=20;i>=0;i--){if(f[x][i] != f[y][i]){x = f[x][i];y = f[y][i];}}//往上跳return f[x][0];
}int main(){IOScin >> n >> m >> s;for(int i=1;i<n;i++){int u , v;cin >> u >> v;ve[u].push_back(v);ve[v].push_back(u);		}//建边dfs(s,0);//建立 st 表和深度 for(int i=1;i<=m;i++){int u , v;cin >> u >> v;cout << lca(u,v) << "\\n";}//求lcareturn 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

1.Dis(求树上两点最近距离)

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 1e5+10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;int n , m , root;
vector<PII>ve[N];
int f[N][30] , d[N] , disx[N][30];void dfs(int x,int fa,int dis){f[x][0] = fa;disx[x][0] = dis;for(int i=1;(1<<i)<=d[x];i++) f[x][i] = f[f[x][i-1]][i-1] , disx[x][i] = disx[x][i-1] + disx[f[x][i-1]][i-1];for(auto [y,l] : ve[x]){if(y == fa) continue;d[y] = d[x] + 1;dfs(y , x , l);}
}int lca(int x,int y){int ans = 0;if(d[x] < d[y]) swap(x , y);for(int i=20;i>=0;i--) if(d[x] - (1 << i) >= d[y]) ans += disx[x][i] , x = f[x][i] ;if(x == y) return ans;for(int i=20;i>=0;i--){if(f[x][i] != f[y][i]){ans += disx[x][i] + disx[y][i];x = f[x][i];y = f[y][i]; }}return ans + disx[x][0] + disx[y][0];
}int main(){IOScin >> n >> m;for(int i=1;i<n;i++){int u , v , w;cin >> u >> v >> w;ve[u].push_back({v,w});ve[v].push_back({u,w});}dfs(1 , 0 , 0);for(int i=1;i<=m;i++){int u , v;cin >> u >> v;cout << lca(u,v) << "\\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

2.聚会

洛谷P4281 聚会
问题：求树上三个点到达同一个点的最小距离 ， 和这个点的编号
结论：三个点两两之间求lca一定有两个相同 ， 不相同的那个就是要求点，最小距离等于两两之间距离和的一半

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 5e5+10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;int n , m , root;
vector<int>ve[N];
int cnt[N] , f[N][21] , d[N][21] , h[N];
int a , b , c;void dfs(int x,int fa,int l){f[x][0] = fa;d[x][0] = l;for(int i=1;(1<<i)<=h[x];i++){f[x][i] = f[f[x][i-1]][i-1];d[x][i] = d[x][i-1] + d[f[x][i-1]][i-1];} 	for(auto k : ve[x]){if(k == fa) continue;h[k] = h[x] + 1;dfs(k,x,1);}}int lca(int x,int y,int &t){int ans = 0;if(h[x] < h[y]) swap(x , y);for(int i=20;i>=0;i--) if(h[x] - (1 << i) >= h[y]) ans += d[x][i] , x = f[x][i]; if(x == y){	t = x;	return ans; }for(int i=20;i>=0;i--){if(f[x][i] != f[y][i]){ans += d[x][i] + d[y][i];x = f[x][i];y = f[y][i];}}t = f[x][0];return ans + d[x][0] + d[y][0];}int r(int x,int y,int z){if(x == y) return z;else if(x == z) return y;else return x;
}int main(){IOScin >> n >> m;for(int i=1;i<n;i++){int u , v;cin >> u >> v;ve[u].push_back(v);ve[v].push_back(u);cnt[u]++;cnt[v]++;}for(int i=1;i<=n;i++) if(cnt[i] == 1) root = i;dfs(root , 0 , 0);for(int i=1;i<=m;i++){int u , v , w , dd;cin >> a >> b >> c;dd = (lca(a,b,u) + lca(b,c,v) + lca(c,a,w)) / 2 ;cout << r(u,v,w) << " " << dd << "\\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

树上差分

用来处理树上的一些区间操作 ， 一般和LCA一起考察

树上点差分 ， 对树上两节点间点权值处理 ：

两个节点 u , v
w = lca(u , v) 
x = f[w][0];
c[u]++;
c[v]++;
c[w]--;
c[x]--;

1. 松鼠的新家

洛谷 P3258 松鼠的新家

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 3e5+10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;int n , a[N];
vector<int>ve[N];
int f[N][21] , d[N] , c[N];void dfs(int x,int fa){f[x][0] = fa;for(int i=1;(1<<i)<=d[x];i++) f[x][i] = f[f[x][i-1]][i-1];for(auto k : ve[x]){if(k == fa) continue;d[k] = d[x] + 1;dfs(k,x);}
}int lca(int x,int y){if(d[x] < d[y]) swap(x,y);for(int i=20;i>=0;i--) if(d[x] - (1<<i) >= d[y]) x = f[x][i];if(x == y) return x;for(int i=20;i>=0;i--){if(f[x][i] != f[y][i]){x = f[x][i];y = f[y][i];}}return f[x][0];
}void dfs1(int x,int fa){for(auto k : ve[x]){if(k == fa) continue;dfs1(k,x);c[x] += c[k];}
}int main(){IOScin >> n;for(int i=1;i<=n;i++) cin >> a[i];for(int i=1;i<n;i++){int u , v;cin >> u >> v;ve[u].push_back(v);ve[v].push_back(u);}dfs(1 , 0);for(int i=1;i<n;i++){int u = a[i] , v = a[i+1];int w = lca(u , v) , x = f[w][0];c[u]++;c[v]++;c[w]--;c[x]--;}dfs1(1,0);for(int i=2;i<=n;i++) c[a[i]]--;//除了第一个点之外的点都被重复计数一次//注意a[i] 存的是点信息 ， c[i]--; 是错误的for(int i=1;i<=n;i++) cout << c[i] << "\\n";return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

树上边差分 ， 对树上两节点间边权值处理 ：

用一个边的子节点代表这个边(无根树以 1 为根 ， 那么 1 的差分数组是无意义的)
两个节点 u , v
w = lca(u , v) 
x = f[w][0];
c[u]++;
c[v]++;
c[w]-= 2;

1. 暗的连锁

思路 ：对于每一条附加边 ， 它可以在树上生成一条环 ， 那么这条环上的每一条主要边都需要砍掉这一条附加边才能断开 ， 每一条附加边都影响自己所构成的环 ， 最后 ， 受到影响 0 次的主要边可以砍掉任意附加边断开 ， 受到影响一次的主要边只能砍影响他的附加边 ， 影响一次及以上的无法断开
计数的时候做树上边差分即可

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 1e5+10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;int n , m , ans;
vector<int>ve[N];
int f[N][21] , d[N] , c[N];void dfs(int x,int fa){f[x][0] = fa;for(int i=1;(1<<i)<=d[x];i++) f[x][i] = f[f[x][i-1]][i-1];for(auto k : ve[x]){if(k == fa) continue;d[k] = d[x] + 1;dfs(k,x);}
}int lca(int x,int y){if(d[x] < d[y]) swap(x,y);for(int i=20;i>=0;i--) if(d[x] - (1<<i) >= d[y]) x = f[x][i];if(x == y) return x;for(int i=20;i>=0;i--){if(f[x][i] != f[y][i]){x = f[x][i];y = f[y][i];}}return f[x][0];
}void dfs1(int x,int fa){for(auto k : ve[x]){if(k == fa) continue;dfs1(k , x);c[x] += c[k];}if(c[x] == 0 && x != 1) ans += m;else if(c[x] == 1) ans += 1;
}int main(){IOScin >> n >> m;for(int i=1;i<n;i++){int u , v;cin >> u >> v;ve[u].push_back(v);ve[v].push_back(u);}dfs(1,0);for(int i=1;i<=m;i++){int u , v , w;cin >> u >> v;w = lca(u,v);c[u]++;c[v]++;c[w] -= 2;}dfs1(1,0);cout << ans;return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);