题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6203

题意：n+1 个点 n 条边的树（点标号 0 ~ n），有若干个点无法通行，导致 p 组 U V 无法连通。问无法通行的点最少有多少个。

解法：按照询问的LCA深度排序，然后顺序标记每个询问的LCA。根据所给的树（任意点为根）预处理出每个点的前序 DFS 序和后序 DFS 序（需统一标号），及点的深度。根据 p 组 U V 处理每组两点的 LCA 。压入优先队列（LCA 深度大的点优先出队）。对于出队的 U V 及其对应的 LCA ，判断点 U 或点 V 是否在之前已禁止的某点的子树中，对于某点U如果在禁止通行的点P的子树中，则L[P]<=L[U]<=R[U]<=R[P]一定成立。所以可以利用树状数组区间更新单点查询，对于每个禁止通行点标记区间L[P],R[P]的所有节点。查询的时候如果L[U]被标记，说明U,V已经被隔断。

#include
using namespace std;
const int maxn = 20100;
typedef long long LL;
vector G[maxn];
int n, m, dfsclk, c[maxn], fa[maxn][21], dep[maxn], L[maxn], R[maxn];
bool vis[maxn];
struct node{
int u,v,uv;
node(){}
node(int u,int v,int uv):u(u),v(v),uv(uv){}
bool operator<(const node &rhs)const{ return dep[uv]=0; i--){
if((dep[u]-dep[v])&(1<=0; i--){
if(fa[u][i]!=fa[v][i]){
u=fa[u][i];
v=fa[v][i];
}
}
return fa[u][0];
}
int lowbit(int x){
return x&(-x);
}
void add(int x, int v){
while(x0){
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
int main()
{
while(~scanf("%d", &n))
{
memset(c, 0, sizeof(c));
memset(vis, 0, sizeof(vis));
memset(dep, 0, sizeof(dep));
for(int i=0; i<=n+1; i++) G[i].clear(); for(int i=1; i<=n; i++){ int u,v; scanf("%d %d", &u,&v); u++,v++; G[u].push_back(v); G[v].push_back(u); } n++; dfsclk = 0; dfs(1); init(); priority_queue q;
scanf("%d", &m);
while(m--){
int u, v;
scanf("%d %d", &u,&v);
u++;
v++;
int uv = LCA(u, v);
q.push(node(u,v,uv));
}
int ans=0;
while(!q.empty()){
node now = q.top();
q.pop();
int flag = query(L[now.u])+query(L[now.v]);
if(flag==0){
ans++;
update(L[now.uv],R[now.uv],1);
}
}
printf("%d\n", ans);
}
return 0;
}