題目鏈接 Paths on the tree

來源? 2014 多校聯合訓練第5場 Problem B

題意就是給出m條樹上的路徑，讓你求出可以同時選擇的互不相交的路徑最大數目。

我們先求出每一條路徑(u, v)中u和v的LCA：w，按照路徑的w的深度大小deep[w]對所有的路徑排序。

deep[w]越大，排在越前面。

然后從第一條路徑開始一次處理，看c[u]和c[v]是否都沒被標記過，如果都沒被標記過則我們把這條路徑選上，把答案加1。

同時標記以w為根的子樹的節點為1，方便后續對c數組的查詢。

時間復雜度$O(mlogn + mlogm + n)$

#include <bits/stdc++.h>using namespace std;#define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i)const int N = 1e5 + 10; const int A = 24;int f[N][A]; int n, m, ans; int deep[N], c[N]; vector <int> v[N];struct node{ int x, y, z;friend bool operator < (const node &a, const node &b){return deep[a.z] > deep[b.z];} } p[N];void dfs(int x, int fa, int dep){deep[x] = dep;if (fa){ f[x][0] = fa;for (int i = 0; f[f[x][i]][i]; ++i) f[x][i + 1] = f[f[x][i]][i];}for (auto u : v[x]){if (u == fa) continue;dfs(u, x, dep + 1);} }int LCA(int a, int b){if (deep[a] < deep[b]) swap(a, b);for (int i = 0, delta = deep[a] - deep[b]; delta; delta >>= 1, ++i) if (delta & 1) a = f[a][i];if (a == b) return a;dec(i, 19, 0) if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];return f[a][0]; }void tag(int x){c[x] = 1;for (auto u : v[x]){if (u == f[x][0]) continue;if (c[u] == 0) tag(u);} }int main(){while (~scanf("%d%d", &n, &m)){memset(f, 0, sizeof f);rep(i, 0, n + 1) v[i].clear();rep(i, 2, n){int x, y;scanf("%d%d", &x, &y);v[x].push_back(y);v[y].push_back(x);}memset(deep, 0, sizeof deep);dfs(1, 0, 0);ans = 0;rep(i, 1, m){int x, y;scanf("%d%d", &x, &y);int z = LCA(x, y);p[i] = {x, y, z};}sort(p + 1, p + m + 1);memset(c, 0, sizeof c);rep(i, 1, m){int u = p[i].x, w = p[i].y;if (c[u] == 0 && c[w] == 0){tag(p[i].z);++ans;}}printf("%d\n", ans);}return 0; }

?

轉載于:https://www.cnblogs.com/cxhscst2/p/7263978.html

總結

以上是生活随笔為你收集整理的HDU 4912 Paths on the tree（LCA+贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

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