點的距離（模板題）

樹中兩點間的距離就是d[u] + d[v] - 2 * d[lca(u, v)]

#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std;const int MAXN = 1e5 + 10; const int MAXM = 20; struct Edge { int to, next; }; Edge e[MAXN << 1]; int head[MAXN], num, n; int up[MAXN][MAXM + 10], d[MAXN];void AddEdge(int from, int to) {e[num] = Edge{to, head[from]};head[from] = num++; }void dfs(int u, int fa) {for(int i = head[u]; ~i; i = e[i].next){int v = e[i].to;if(v == fa) continue;d[v] = d[u] + 1;up[v][0] = u;dfs(v, u);} }void get_up() {_for(j, 1, MAXM)_for(i, 1, n)up[i][j] = up[up[i][j-1]][j-1]; }int lca(int u, int v) {if(d[u] < d[v]) swap(u, v);for(int i = MAXM; i >= 0; i--)if(d[up[u][i]] >= d[v]) u = up[u][i];if(u == v) return u;for(int i = MAXM; i >= 0; i--)if(up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];return up[u][0]; }int main() {memset(head, -1, sizeof(head)); num = 0; scanf("%d", &n);REP(i, 1, n){int u, v;scanf("%d%d", &u, &v);AddEdge(u, v); AddEdge(v, u); }dfs(1, -1);get_up();int q; scanf("%d", &q);while(q--){int u, v;scanf("%d%d", &u, &v);printf("%d\n", d[u] + d[v] - 2 * d[lca(u, v)]);}return 0; }

暗的連鎖

這道題首先有個轉化

切兩刀能不能切斷，取決于非樹邊，因為非樹邊會構成環

那么可以把非樹邊構成的環上所有的樹邊都覆蓋一次

如果只覆蓋一次，那么顯然有唯一解

如果沒有被覆蓋，那就加上非樹邊的數目，因為第二刀可以切任意一條非樹邊

如果覆蓋兩次以上，那么兩刀是不能解決問題的。

所以就有維護每條邊被覆蓋了多少次

這里用到了樹上差分，f[u]表示u與u的父親連的邊的覆蓋次數

對于非樹邊u, v，讓f[u]++, f[v]++, f[lca(u, v)]--

最后在“前綴和回來”，即統計所有子樹的值加起來，就是答案

最后注意計算答案的時候根的f數組不算，因為根沒有父親

#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std;const int MAXN = 1e5 + 10; const int MAXM = 20; struct Edge{ int to, next; }; Edge e[MAXN << 1]; int head[MAXN], num, n, m; int up[MAXN][MAXM + 10], d[MAXN]; int f[MAXN];void read(int& x) {int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f; }void AddEdge(int to, int from) {e[num] = Edge{to, head[from]};head[from] = num++; }void dfs(int u, int fa) {for(int i = head[u]; ~i; i = e[i].next){int v = e[i].to;if(v == fa) continue;d[v] = d[u] + 1;up[v][0] = u;dfs(v, u);} }int dp(int u, int fa) {for(int i = head[u]; ~i; i = e[i].next){int v = e[i].to;if(v == fa) continue;dp(v, u);f[u] += f[v];} }void init() {dfs(1, -1);_for(j, 1, MAXM)_for(i, 1, n)up[i][j] = up[up[i][j - 1]][j - 1]; }int lca(int u, int v) {if(d[u] < d[v]) swap(u, v);for(int i = MAXM; i >= 0; i--)if(d[up[u][i]] >= d[v])u = up[u][i];if(u == v) return u;for(int i = MAXM; i >= 0; i--)if(up[u][i] != up[v][i])u = up[u][i], v = up[v][i];return up[u][0]; }int main() {read(n);read(m);memset(head, -1, sizeof(head)); num = 0;REP(i, 1, n){int u, v; read(u), read(v);AddEdge(u, v); AddEdge(v, u); }init(); _for(i, 1, m){int u, v; read(u), read(v);f[u]++; f[v]++; f[lca(u, v)] -= 2;}dp(1, -1);int ans = 0;_for(i, 2, n){if(f[i] == 1) ans++;if(f[i] == 0) ans += m;}printf("%d\n", ans);return 0; }

?

轉載于:https://www.cnblogs.com/sugewud/p/9819317.html

總結

以上是生活随笔為你收集整理的LCA题集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。