題意

nn 臺服務器構成一棵樹，給定 pp 對無法通信的服務器對，求最少有多少臺服務器出現故障。
1≤n≤100001≤n≤10000
1≤p≤500001≤p≤50000

思路

貪心比較明顯，先考慮一個貪心的順序。先處理出每個服務器對的 LCALCA ，假設比某對服務器 LCALCA 更深的服務器都已經斷過了，那我們肯定要盡量往高的斷，而且也只有 LCALCA 從深到淺的斷才能保證決策清晰。由此得出算法：先對 LCALCA 由深到淺排序，每次都把 LCALCA 弄斷，并把以這個 LCALCA 為根的子樹中節點標記。服務器對中的某個點已經被標記過了，那么這次操作可以跳過（因為標記它的 LCALCA 肯定比現在的深，就說明這個點在半路上就已經斷掉了）。而標記可以使用 dfsdfs 序，再用樹狀數組區間改單點查。但何必呢？一個點被標記說明它的子樹一定全被標記了，那就直接用 dfsdfs 標記，發現某個點已被標記直接返回即可。復雜度和 pp<script type="math/tex" id="MathJax-Element-1247">p</script> 個操作的復雜度是相加的，比樹狀數組不增反減。

代碼

#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define FOR(i,x,y) for(int i=(x);i<=(y);i++) #define DOR(i,x,y) for(int i=(x);i>=(y);i--) #define lowbit(x) ((x)&-(x)) #define N 10003 typedef long long LL; using namespace std; int bin[N],ans; template<const int maxn,const int maxm>struct Linked_list {int head[maxn],to[maxm],nxt[maxm],tot;void clear(){memset(head,-1,sizeof(head));tot=0;}void add(int u,int v){to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}#define EOR(i,G,u) for(int i=G.head[u];~i;i=G.nxt[i]) }; struct data {int a,b,lca,lcaLV;bool operator <(const data &_)const{return lcaLV>_.lcaLV;} }; struct Tree {int lv[N],fa[N][20],mark[N],n;data D[N*5];Linked_list<N,N<<1>G;void reset(int _){n=_;G.clear();memset(mark,0,sizeof(mark));memset(fa,-1,sizeof(fa));}void add(int u,int v){G.add(u,v);G.add(v,u);}void dfs(int u,int d){lv[u]=d;EOR(i,G,u){int v=G.to[i];if(v!=fa[u][0]){fa[v][0]=u;dfs(v,d+1);}}}void redfs(int u){if(mark[u])return;mark[u]=1;EOR(i,G,u){int v=G.to[i];if(v!=fa[u][0])redfs(v);}}void make_fa(){FOR(j,1,19)FOR(i,1,n)if(~fa[i][j-1])fa[i][j]=fa[fa[i][j-1]][j-1];}void jmp(int &x,int stp){while(stp){x=fa[x][bin[lowbit(stp)]];stp^=lowbit(stp);}}int LCA(int a,int b){if(lv[a]>lv[b])jmp(a,lv[a]-lv[b]);else if(lv[b]>lv[a])jmp(b,lv[b]-lv[a]);if(a==b)return a;DOR(i,19,0)if(fa[a][i]!=fa[b][i]){a=fa[a][i];b=fa[b][i];}return fa[a][0];}void Read_data(int Q){FOR(i,1,Q){scanf("%d%d",&D[i].a,&D[i].b);D[i].a++,D[i].b++;D[i].lcaLV=lv[D[i].lca=LCA(D[i].a,D[i].b)];}sort(D+1,D+1+Q);}void destro(int k){if(mark[D[k].a]||mark[D[k].b])return;redfs(D[k].lca);ans++;} }T;int main() {FOR(i,2,N-3)bin[i]=bin[i>>1]+1;int n,m;while(~scanf("%d",&n)){n++;ans=0;T.reset(n);FOR(i,1,n-1){int u,v;scanf("%d%d",&u,&v);T.add(u+1,v+1);}T.dfs(1,0);T.make_fa();scanf("%d",&m);T.Read_data(m);FOR(i,1,m)T.destro(i);printf("%d\n",ans);}return 0; }

總結

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

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