题目大意：
给你一棵树，其中有一些点是坏掉的。告诉你k个点对表示这两个点的路径上至少有1个点是坏掉的。问整棵树上至少有多少点是坏的。
思路：
贪心。
找出每组点对的LCA，对所有点对按照LCA的深度排序。
然后枚举每一组点对，如果当前的两个结点u和v都没有被标记，则把以其LCA为根的子树标记成坏的，并将LCA算入答案。
如果当前的两个结点u和v至少有一个被标记，则说明两个结点已经不连通，不需要将其LCA计入答案。
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#include<functional>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int V=,logV=;
std::vector<int> e[V];
inline void addedge(const int &u,const int &v) {
e[u].push_back(v);
e[v].push_back(u);
}
int dep[V],anc[V][logV];
inline int _log2(const float &x) {
return ((unsigned&)x>>&)-;
}
void dfs(const int &x,const int &p) {
dep[x]=dep[p]+;
anc[x][]=p;
for(int i=;i<=_log2(dep[x]);i++) {
anc[x][i]=anc[anc[x][i-]][i-];
}
for(unsigned i=;i<e[x].size();i++) {
const int &y=e[x][i];
if(y==p) continue;
dfs(y,x);
}
}
inline int getlca(int x,int y) {
if(dep[x]<dep[y]) std::swap(x,y);
for(register int i=_log2(dep[x]);i>=;i--) {
if(dep[anc[x][i]]>=dep[y]) {
x=anc[x][i];
}
}
if(x==y) return x;
for(register int i=_log2(dep[x]);i>=;i--) {
if(anc[x][i]!=anc[y][i]) {
x=anc[x][i];
y=anc[y][i];
}
}
return anc[x][];
}
struct Path {
int u,v,lca;
Path(const int &u,const int &v,const int &lca) {
this->u=u;
this->v=v;
this->lca=lca;
}
bool operator > (const Path &another) const {
return dep[lca]>dep[another.lca];
}
};
std::vector<Path> lca;
bool mark[V];
void modify(const int &x) {
if(mark[x]) return;
mark[x]=true;
for(unsigned i=;i<e[x].size();i++) {
const int &y=e[x][i];
if(y==anc[x][]) continue;
modify(y);
}
e[x].clear();
}
inline void init() {
for(register int i=;i<V;i++) e[i].clear();
lca.clear();
memset(mark,,sizeof mark);
}
int main() {
register int n;
while(~scanf("%d\n",&n)) {
init();
for(;n;n--) {
addedge(getint(),getint());
}
dfs(,);
for(register int k=getint();k;k--) {
const int &u=getint(),&v=getint();
lca.push_back(Path(u,v,getlca(u,v)));
}
std::sort(lca.begin(),lca.end(),std::greater<Path>());
int ans=;
for(register unsigned i=;i<lca.size();i++) {
const int &u=lca[i].u,&v=lca[i].v,&a=lca[i].lca;
if(mark[u]||mark[v]) continue;
modify(a);
ans++;
}
printf("%d\n",ans);
}
return ;
}