首页 > 代码库 > HDU 4912 Paths on the tree（LCA+贪心）
HDU 4912 Paths on the tree（LCA+贪心）
题目链接 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;}
HDU 4912 Paths on the tree（LCA+贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。