题目大意：

　　给你一棵树，其中有一些点是坏掉的。告诉你k个点对表示这两个点的路径上至少有1个点是坏掉的。问整棵树上至少有多少点是坏的。

思路：

　　贪心。

　　找出每组点对的LCA，对所有点对按照LCA的深度排序。

　　然后枚举每一组点对，如果当前的两个结点u和v都没有被标记，则把以其LCA为根的子树标记成坏的，并将LCA算入答案。

　　如果当前的两个结点u和v至少有一个被标记，则说明两个结点已经不连通，不需要将其LCA计入答案。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            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
           
             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
            
             =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
             
               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
              
               ()); 93 int ans=0; 94 for(register unsigned i=0;i