【每日一题】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]个整数代表本次询问中需要考虑的帮派。

题解

通过分析知道，一个帮派可以控制的所有城市为以这些城市的公共祖先为根节点的子树去掉这颗树的一部分小子树，对多个帮派同理，些帮派占领城市的公共祖先Top就是每个帮派所控制城市公共祖先的公共祖先，那么首都到以该帮派控制城市的最短距离就是首都u到某个控制城市的距离。

①若u不在Top为根的子树中，设w=lca(u,Top),答案就是:

就是直接从u到Top。

②若u在Top为根的子树中,可以知道答案就是u与离u最近两点（一前一后，设为v）与u的最近公共祖先（设为w）的距离，答案就是:

如何求v，对于每个帮派，把其控制的城市的dfs序升序排好，二分查询首都dfs序处于的区间的位置，把一前一后的两个v求出来，答案取最小即可。

附代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int maxn = 5e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
int n,m,q,cnt,p[maxn][20],dep[maxn],dfn[maxn],id[maxn],top[maxn],a[maxn];
vector<int>g[maxn],vec[maxn];
void dfs(int u,int fa){
    id[cnt]=u;
    dfn[u]=cnt++;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==fa)continue;
        dep[v]=dep[u]+1;
        p[v][0]=u;
        dfs(v,u);
    }
}
int lca(int a,int b){
    int i,j;
    if(dep[a]<dep[b])swap(a,b);
    for(i=0;(1<<i)<=dep[a];i++);
    i--;
    for(j=i;j>=0;j--)
        if(dep[a]-(1<<j)>=dep[b])
            a=p[a][j];
    if(a==b)return a;
    for(j=i;j>=0;j--)
        if(p[a][j]&&p[a][j]!=p[b][j])
            a=p[a][j],b=p[b][j];
    return p[a][0];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    dep[1]=cnt=1;
    dfs(1,0);
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++)
            if(p[i][j-1])p[i][j]=p[p[i][j-1]][j-1];
    cin>>m;
    for(int i=1;i<=m;i++){
        int num,u;cin>>num;
        for(int j=1;j<=num;j++){
            cin>>u;
            vec[i].push_back(dfn[u]);
            if(j==1)top[i]=u;
            else top[i]=lca(top[i],u);
        }
        sort(vec[i].begin(),vec[i].end());
    }
    cin>>q;
    while(q--){
        int u,num,Top,ans=n;
        cin>>u>>num;
        for(int i=1;i<=num;i++){
            cin>>a[i];
            if(i==1)Top=top[a[i]];
            else Top=lca(Top,top[a[i]]);
        }
        int fa=lca(u,Top);
        if(fa!=Top){
            cout<<abs(dep[u]-dep[fa])+abs(dep[fa]-dep[Top])<<'\n';continue;
        }
        for(int i=1;i<=num;i++){
            int now=lower_bound(vec[a[i]].begin(),vec[a[i]].end(),dfn[u])-vec[a[i]].begin();
            if(now!=vec[a[i]].size()){
                int v=lca(u,id[vec[a[i]][now]]);
                ans=min(ans,abs(dep[u]-dep[v]));
            }
            if(now!=0){
                int v=lca(u,id[vec[a[i]][now-1]]);
                ans=min(ans,abs(dep[u]-dep[v]));
            }
        }
        cout<<ans<<'\n';
    }
}