Source：2017 ACM/ICPC Asia Regional Shenyang Online

Problem：給你一顆樹，告訴你m對點是走不通的，問最少有幾個壞點。

Idea：如果注意到按照lca的深度來貪心，當前u，v走得通就取那個lca，使得他的子樹都無法再連出去，那么結果一定是最優(yōu)的，剩下的用樹狀數(shù)組或者線段樹維護下就好了。

Code:

#include<bits/stdc++.h> using namespace std;#define fi first #define se second #define pb push_back #define CLR(A, X) memset(A, X, sizeof(A)) #define bitcount(X) __builtin_popcountll(X) typedef long long LL; typedef pair<int, int> PII; const double eps = 1e-10; const LL MOD = 1e9+7; const auto INF = 0x3f3f3f3f; int dcmp(double x) { if(fabs(x) < eps) return 0; return x<0?-1:1; }const int MAXN = 1e4+5;struct BIT{int c[MAXN];int sum(int x) { int res=0; while(x) res+=c[x], x-=(x&-x); return res; }void add(int x, int d) { while(x<MAXN) c[x]+=d, x+=(x&-x); }void reset() { CLR(c,0); } }A;struct Node {int u, v, root, deep;bool operator < (const Node &A) const {return deep > A.deep;} };int p[MAXN][25], deep[MAXN], dfn[MAXN], sz[MAXN], dfs_clock; vector<int> G[MAXN]; vector<Node> g;void dfs(int u, int fa) {for(int i = 1; i <= 20; i++) {p[u][i] = p[p[u][i-1]][i-1];}dfn[u] = ++dfs_clock, sz[u] = 1;for(int v:G[u]) if(v != fa) {deep[v] = deep[u]+1;p[v][0] = u;dfs(v, u);sz[u] += sz[v];} }int lca(int a, int b) {if(deep[a] < deep[b]) swap(a, b);int t = deep[a] - deep[b];for(int i = 0; (1<<i) <= t; i++) if((1<<i)&t) a = p[a][i];for(int i = 20; i >= 0; i--) {if(p[a][i] != p[b][i]) a = p[a][i], b = p[b][i];}return a==b?a:p[a][0]; }int main() {int n, u, v, m;while(~scanf("%d", &n)) {for(int i = 0; i <= n; i++) G[i].clear();A.reset(), g.clear(), dfs_clock = 0, p[0][0] = 0;for(int i = 1; i <= n; i++) {scanf("%d%d", &u, &v);G[u].pb(v), G[v].pb(u);}dfs(0, -1);scanf("%d", &m);while(m--) {scanf("%d%d", &u, &v);int root = lca(u, v);g.pb((Node){u, v, root, deep[root]});}sort(g.begin(), g.end());int ans = 0;for(Node x:g) {if(A.sum(dfn[x.u]) || A.sum(dfn[x.v])) continue;A.add(dfn[x.root], 1), A.add(dfn[x.root]+sz[x.root], -1);ans++;}printf("%d\n", ans);}return 0; }

總結

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

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