[2018.03.13 T3]联盟(alliances)

暂无链接

联盟(alliances)

【题目描述】

树国是一个有 n 个城市的国家，城市编号为 1∼n。连接这些城市的道路网络形如一棵树，即任意两个城市之间有恰好一条路径。城市中有 k 个帮派，编号为 1∼k。每个帮派会占据一些城市，以进行非法交易。有时帮派之间会结盟，这就使得城市更加不安全了。同一座城市中可能有多个帮派。

当一些帮派结成联盟时，他们会更加强大，同时也更加危险。他们所控制的城市数会显著增加。具体地，一个联盟控制的城市是联盟中所有帮派所占据的城市，再加上这些城市两两之间路径上的所有城市。

shy 是树国的市长，他想要选择一个城市作为首都。在决定之前，他要先做一些调研。为此，他找来你帮他回答一些询问，你能做到吗？在每个询问中，shy 会选择一个城市作为首都，同时会告诉你当前活跃的帮派的集合。在这个询问中，你只需要考虑给定的集合中的帮派，其他的帮派你可以当作不存在。已知给定集合中的这些帮派结成了联盟，shy 希望抓获联盟中的人，以得到关于整个联盟的一些信息。为此，他要找到被联盟控制的所有城市中离首都最近的一座城市到首都的距离。有可能首都本身就被控制了，此时答案为 0。请注意，询问之间相互独立，互不影响。

【输入】

输入的第一行包含一个整数 n，代表树国中的城市数。

接下来 n−1 行，每行包含两个整数 u 和 v，代表城市 u和 v 之间存在一条道路。

接下来一行包含一个整数 k，代表树国中的帮派数。

接下来 k 行，每行描述一个帮派。第 i 行的第一个整数 c[i] 代表第 i 个帮派占据的城市数，接下来 c[i]个整数，代表被第 i 个帮派占据的城市。

接下来一行包含一个整数 Q，代表询问数。

接下来 Q 行，每行描述一个询问。每行的前两个整数 V 和 t[i]代表本次询问中的首都与需要考虑的帮派集合的大小。接下来t[i]个整数代表本次询问中需要考虑的帮派。

【输出】

对于每个询问，输出一行，包含一个整数，代表询问的答案。

【输入样例】

7
1 2
1 3
2 4
2 5
3 6
3 7
2
2 6 7
1 4
3
5 1 2
1 1 1
5 2 1 2

【输出样例】

2
1
1

【提示】

【数据规模】

（1）对于 30%的数据，1≤n,k,Q≤1000, 1≤每个帮派占据城市数之和≤1000, 1≤每个询问中考虑的帮派数之和≤1000；

（2）对于 60%的数据，1≤n,k,Q≤100000, 1≤每个帮派占据城市数之和≤100000, 1≤每个询问中考虑的帮派数之和≤100000；

（3）对于 100%的数据，1≤n,k,Q≤500000, 1≤每个帮派占据城市数之和≤500000, 1≤每个询问中考虑的帮派数之和≤500000。

题解

我们考虑首都与帮派势力的位置关系：

首先，帮派的势力范围肯定被包含在一个子树中。在这个子树中，有的是被帮派控制的，有的没有。

1.首都不在这个子树内
显然，这个时候，最短距离等于首都与子树根节点的距离。这个时候，我们求解两点LCA的时候，显然LCA不等于根节点，很好判断。

2.首都在子树内
在子树内的情况和上面的判断方法一样，如果首都和子树根节点的LCA为根节点本身，显然首都在子树内。这时，还分为两种情况：

(1)首都已经被控制
(2)首都未被控制
这两种情况要判比较困难，我们需要用到dfs序，每次查找首都dfs序的前驱和后继而且原来就被控制的点。因为如果首都未被控制的话，首都一定会连在帮派势力的联通快的末端上，而这个点一定是首都dfs序的前驱或者后缀；而且，处在末端的被帮派控制的点一定是初始就被控制的点。我们只需要求出首都的一开始就被控制的点的前驱后缀，求一下LCA，如果LCA就是自己，那么首都一定被连在那颗子树里了，即一定被控制了，输出零。如果不是，只需要求一下距离，取一下小就好了。

其实这里找前驱后继显然是要二分的，但是数据水，博主又懒，所以暴力枚举。。。

题解

#include<bits/stdc++.h>
using namespace std;
const int M=1e6+5;
struct node{int size,dad,son,top,deep;
};
node tree[M];
int n,k,q,num,head[M],xu2[M],que[M];
vector<int>edge[M];
vector<int>gang[M];
void in()
{int a,b;scanf("%d",&n);for(int i=1;i<n;++i){scanf("%d%d",&a,&b);edge[a].push_back(b);edge[b].push_back(a);}
}
int dfs1(int v,int f,int d)
{xu2[v]=++num;tree[v].dad=f;tree[v].deep=d;tree[v].size=1;int bigs=-1;for(int i=edge[v].size()-1;i>=0;--i){if(edge[v][i]==f)continue;tree[v].size+=dfs1(edge[v][i],v,d+1);if(bigs<tree[edge[v][i]].size)bigs=tree[edge[v][i]].size,tree[v].son=edge[v][i];}return tree[v].size;
}
void dfs2(int v,int top)
{tree[v].top=top;if(!tree[v].son)return;dfs2(tree[v].son,top);for(int i=edge[v].size()-1;i>=0;--i){if(edge[v][i]!=tree[v].dad&&edge[v][i]!=tree[v].son)dfs2(edge[v][i],edge[v][i]);}
}
int lca(int a,int b)
{while(tree[a].top!=tree[b].top){if(tree[tree[a].top].deep<tree[tree[b].top].deep)b=tree[tree[b].top].dad;else a=tree[tree[a].top].dad;}if(tree[a].deep<tree[b].deep)return a;return b;
}
int work(int cap,int h)
{int kk=lca(cap,h);if(kk!=h)return tree[cap].deep+tree[h].deep-2*tree[kk].deep;int p1=0,p2=M-5,h1,h2;for(int i=1;i<=que[0];++i){for(int j=gang[que[i]].size()-1;j>=0;--j){if(xu2[gang[que[i]][j]]<=xu2[cap])if(xu2[gang[que[i]][j]]>=xu2[p1])p1=gang[que[i]][j];if(xu2[gang[que[i]][j]]>=xu2[cap])if(xu2[gang[que[i]][j]]<=xu2[p2])p2=gang[que[i]][j];}}int ans=1e9;if(p1>0)h1=lca(p1,cap),ans=tree[cap].deep-tree[h1].deep;if(p2<M-5)h2=lca(p2,cap),ans=min(ans,tree[cap].deep-tree[h2].deep);return ans;
}
void ac()
{xu2[0]=-1;xu2[M-5]=1e9;dfs1(1,0,1);dfs2(1,1);scanf("%d",&k);int hh,a,h;for(int i=1;i<=k;++i){scanf("%d%d",&hh,&h);gang[i].push_back(h);for(int j=2;j<=hh;++j)scanf("%d",&a),gang[i].push_back(a),h=lca(h,a);head[i]=h;}scanf("%d",&q);int cap;for(int i=1;i<=q;++i){que[0]=0;scanf("%d%d%d",&cap,&hh,&h);que[++que[0]]=h;h=head[h];for(int j=2;j<=hh;++j){scanf("%d",&a);que[++que[0]]=a;h=lca(h,head[a]);}printf("%d\n",work(cap,h));}
}
int main()
{in();ac();return 0;
}