题目大意：
给你一棵树，其中有一些点是坏掉的。告诉你k个点对表示这两个点的路径上至少有1个点是坏掉的。问整棵树上至少有多少点是坏的。
思路：
贪心。
找出每组点对的LCA，对所有点对按照LCA的深度排序。
然后枚举每一组点对，如果当前的两个结点u和v都没有被标记，则把以其LCA为根的子树标记成坏的，并将LCA算入答案。
如果当前的两个结点u和v至少有一个被标记，则说明两个结点已经不连通，不需要将其LCA计入答案。
1 #include<cstdio> 2 #include<cctype> 3 #include<vector> 4 #include<cstring> 5 #include<algorithm> 6 #include<functional> 7 inline int getint() { 8 register char ch; 9 while(!isdigit(ch=getchar())); 10 register int x=ch^'0'; 11 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 12 return x; 13 } 14 const int V=10001,logV=14; 15 std::vector<int> e[V]; 16 inline void addedge(const int &u,const int &v) { 17 e[u].push_back(v); 18 e[v].push_back(u); 19 } 20 int dep[V],anc[V][logV]; 21 inline int _log2(const float &x) { 22 return ((unsigned&)x>>23&255)-127; 23 } 24 void dfs(const int &x,const int &p) { 25 dep[x]=dep[p]+1; 26 anc[x][0]=p; 27 for(int i=1;i<=_log2(dep[x]);i++) { 28 anc[x][i]=anc[anc[x][i-1]][i-1]; 29 } 30 for(unsigned i=0;i<e[x].size();i++) { 31 const int &y=e[x][i]; 32 if(y==p) continue; 33 dfs(y,x); 34 } 35 } 36 inline int getlca(int x,int y) { 37 if(dep[x]<dep[y]) std::swap(x,y); 38 for(register int i=_log2(dep[x]);i>=0;i--) { 39 if(dep[anc[x][i]]>=dep[y]) { 40 x=anc[x][i]; 41 } 42 } 43 if(x==y) return x; 44 for(register int i=_log2(dep[x]);i>=0;i--) { 45 if(anc[x][i]!=anc[y][i]) { 46 x=anc[x][i]; 47 y=anc[y][i]; 48 } 49 } 50 return anc[x][0]; 51 } 52 struct Path { 53 int u,v,lca; 54 Path(const int &u,const int &v,const int &lca) { 55 this->u=u; 56 this->v=v; 57 this->lca=lca; 58 } 59 bool operator > (const Path &another) const { 60 return dep[lca]>dep[another.lca]; 61 } 62 }; 63 std::vector<Path> lca; 64 bool mark[V]; 65 void modify(const int &x) { 66 if(mark[x]) return; 67 mark[x]=true; 68 for(unsigned i=0;i<e[x].size();i++) { 69 const int &y=e[x][i]; 70 if(y==anc[x][0]) continue; 71 modify(y); 72 } 73 e[x].clear(); 74 } 75 inline void init() { 76 for(register int i=0;i<V;i++) e[i].clear(); 77 lca.clear(); 78 memset(mark,0,sizeof mark); 79 } 80 int main() { 81 register int n; 82 while(~scanf("%d ",&n)) { 83 init(); 84 for(;n;n--) { 85 addedge(getint(),getint()); 86 } 87 dfs(0,0); 88 for(register int k=getint();k;k--) { 89 const int &u=getint(),&v=getint(); 90 lca.push_back(Path(u,v,getlca(u,v))); 91 } 92 std::sort(lca.begin(),lca.end(),std::greater<Path>()); 93 int ans=0; 94 for(register unsigned i=0;i<lca.size();i++) { 95 const int &u=lca[i].u,&v=lca[i].v,&a=lca[i].lca; 96 if(mark[u]||mark[v]) continue; 97 modify(a); 98 ans++; 99 } 100 printf("%d ",ans); 101 } 102 return 0; 103 }