題意：給出一棵樹(shù)，然后給出一些點(diǎn)對(duì)，要求這些點(diǎn)對(duì)無(wú)法連通（可以毀壞u到v路上的點(diǎn)，也可以毀壞u，也可以毀壞v）。問(wèn)最少毀壞多少個(gè)點(diǎn)。

解法：很容易想到，如果毀壞u和v的最近公共祖先，那么這條路是斷的，而且u的子樹(shù)上的點(diǎn)到v的子樹(shù)上的點(diǎn)也會(huì)無(wú)法連通。但是單憑LCA是不夠的，因?yàn)樯疃仍酱蟮膽?yīng)該優(yōu)先解決，深度小的點(diǎn)無(wú)法影響深度大的點(diǎn)。所以我們要貪心一下，每次取出點(diǎn)對(duì)的LCA深度小的點(diǎn)對(duì)。如果這個(gè)點(diǎn)對(duì)u和v都沒(méi)有標(biāo)記過(guò)，那么我們就把他們的LCA的整個(gè)子樹(shù)給標(biāo)記了。如果標(biāo)記過(guò)了，那么就不需要處理。

整理一下思路，首先圍繞LCA，然后我們要做標(biāo)記整個(gè)子樹(shù)的操作，標(biāo)號(hào)的話要用dfs序，修改的話肯定不能用暴力，太慢了，所以想到用線段樹(shù)。

最后需要用上LCA + dfs序 + 線段樹(shù)。

別人很多用的樹(shù)狀數(shù)組，但是我不會(huì)樹(shù)狀數(shù)組的區(qū)間更新，所以自己搞了搞線段樹(shù)。代碼也是超級(jí)長(zhǎng)。。。

代碼如下：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <queue> using namespace std; inline int read() {char ch = getchar();int f = 1, x = 0;while(!(ch >= '0' && ch <= '9')) {if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * f; }const int Maxn = 1e4 + 5; int val;struct seg {int l, r;long long sum, lazy; }segtree[Maxn * 4];void build(int node, int l, int r) {segtree[node].l = l;segtree[node].r = r;segtree[node].lazy = 0;if(l == r) {segtree[node].sum = 0;return;} else {int mid = (l + r) >> 1;build(node << 1, l, mid);build(node << 1 | 1, mid + 1, r);segtree[node].sum = segtree[node << 1].sum + segtree[node << 1 | 1].sum;} }void pushdown(int node) {if(segtree[node].lazy != 0) {segtree[node<<1].lazy = 1;segtree[node<<1|1].lazy = 1;segtree[node<<1].sum = 1;segtree[node<<1|1].sum = 1;segtree[node].lazy = 0;} }long long query(int node, int x, int y) {if(segtree[node].l == x && segtree[node].r == y) {return segtree[node].sum;}pushdown(node);int mid = segtree[node].l + segtree[node].r;long long res = 0;mid >>= 1;if(mid >= y)res += query(node << 1, x, y);else if(mid < x)res += query(node << 1 | 1, x, y);else {res += query(node << 1, x, mid);res += query(node << 1 | 1, mid + 1, y);}return res; }void update(int node, int x, int y) {if(segtree[node].l == x && segtree[node].r == y) {segtree[node].lazy = val;segtree[node].sum = val;return;}pushdown(node);int mid = segtree[node].l + segtree[node].r;mid >>= 1;if(mid >= y)update(node << 1, x, y);else if(mid < x)update(node << 1 | 1, x, y);else {update(node << 1, x, mid);update(node << 1 | 1, mid + 1, y);} // segtree[node].sum = segtree[node << 1].sum + segtree[node << 1 | 1].sum; }const int maxn = 1e4 + 5; const int M = 20; //樹(shù)的深度 int dp[2 * maxn][M]; //這個(gè)數(shù)組記得開(kāi)到2*maxn，因?yàn)楸闅v后序列長(zhǎng)度為2*n-1 bool vis[maxn]; struct edge {int u, v, w, next; } e[2 * maxn]; int tot, head[maxn]; int in[maxn], out[maxn];struct Node {int u, v, lca, dep;Node(){}Node(int a, int b, int c, int d) {u = a, v = b, lca = c, dep = d;}bool operator < (const Node& t) const {if(dep < t.dep)return 1;return 0;} };inline void add(int u ,int v ,int w ,int &k) {e[k].u = u; e[k].v = v; e[k].w = w;e[k].next = head[u]; head[u] = k++;u = u ^ v; v = u ^ v; u = u ^ v;e[k].u = u; e[k].v = v; e[k].w = w;e[k].next = head[u]; head[u] = k++; }int ver[2 * maxn], R[2 * maxn], first[maxn], dir[maxn]; // ver:節(jié)點(diǎn)編號(hào) R：深度 first：首位 dir：距離void dfs(int u ,int dep, int& num2) {vis[u] = true; ver[++tot] = u; first[u] = tot; R[tot] = dep; in[u] = ++num2;for(int k = head[u]; ~k; k = e[k].next)if( !vis[e[k].v] ) {int v = e[k].v , w = e[k].w;dir[v] = dir[u] + w;dfs(v, dep + 1, num2);ver[++tot] = u; R[tot] = dep;}out[u] = num2; }void ST(int n) {for(int i = 1; i <= n; i++)dp[i][0] = i;for(int j = 1; (1<<j) <= n; j++) {for(int i = 1; i + (1<<j) - 1 <= n; i++) {int a = dp[i][j-1] , b = dp[i + (1<<(j - 1))][j - 1];dp[i][j] = R[a] < R[b] ? a : b; //i - i + 2 ^ j - 1中深度最小的編號(hào) }} }int RMQ(int l, int r) {int k = 0;while((1<<(k + 1)) <= r - l + 1)k++;int a = dp[l][k], b = dp[r - (1<<k) + 1][k]; //保存的是編號(hào)return R[a] < R[b] ? a : b; }int LCA(int u ,int v) {int x = first[u] , y = first[v];if(x > y) swap(x,y);int res = RMQ(x,y);return ver[res]; }priority_queue <Node> que; int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin);//freopen("Out.txt","w",stdout); #endifint n, q, num, num2;while(scanf("%d", &n) != EOF) {memset(head, -1, sizeof(head));memset(vis, false, sizeof(vis));n++;num = 0;num2 = 0;for(int i = 1; i < n; i++) {int u = read() + 1, v = read() + 1, val = 1;add(u, v, val, num);}tot = 0; dir[1] = 0;dfs(1, 1, num2);ST(2 * n - 1);scanf("%d", &q);while(q--) {int x = read() + 1, y = read() + 1;int lca = LCA(x, y);que.push(Node(x, y, lca, R[first[lca]]));}int ans = 0;build(1, 1, n);val = 1;while(!que.empty()) {Node now = que.top();que.pop();int x = query(1, in[now.u], in[now.u]), y = query(1, in[now.v], in[now.v]);if(x || y) {continue;} else {update(1, in[now.lca], out[now.lca]);ans++;}}printf("%d\n", ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU 6203ping ping ping(LCA+贪心)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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