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]个整数代表本次询问中需要考虑的帮派。.

输出描述:

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

题解

~~为什么感觉每日一题越来越南了呜呜呜~~

Part One：前置理解

我们先来理解一下这句话一个联盟控制的城市是联盟中所有帮派所占据的城市，再加上这些城市两两之间路径上的所有城市
我们举一个例子
图片说明
假如橘色的节点分别是两个帮派的，那这两个帮派结盟后控制的范围就是他们共同在的子树，如图

Part Two：正题

我们要求的是被联盟控制的所有城市中离首都最近的一座城市到首都的距离，对于本题，大的方面有以下三种情况

首都与被控制的子树不在同一个城市

红色为首都，黄色为帮派所在城市。这是首都与被控制的子树不在同一个城市，此时离首都最近的点就是两个帮派所占城市的 $lca$ ,所以，此时 $ans=dep[首都]+dep[lca(帮派城市)]-dep[lca(帮派城市,首都)]$
首都被控制
此时答案显然为0，但是首都被控制也可能是首都被直接控制，或者首都的前驱后继被控制了。
首都未被控制但与被控制的城市在一个子树当中

此时红色线圈起来的是被控制的城市，首都和他们在同一个子树里，但首都没有被控制。这时候就是首都的前驱后继被间接控制了。
对于第二三种情况都与首都的前驱后继有关系，我们可以一起讨论。
下面的问题就是我们怎么去找节点的前驱后继呢？
那就是dfs序啦。在查找前驱后继的时候利用二分查找降低复杂度即可。所以这道题我们就可以利用 $lca$ +$dfs序解决啦。
如果大家不会dfs序的话，建议大家去b站看看卿学姐关于dfs序的视频，我就偷个懒不过多展开了。附上视频地址吧：https://www.bilibili.com/video/BV1Ys411q7EN?from=search&seid=1255713242376716876 (众所周知，B站是个学习的地方)
代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=5e5+100;
int dep[N],dp[N][25],id[N],head[N],hight[N],bang[N],yuan[N];
vector<int> a[N];
struct node{
    int now,to,net;
}s[N<<1];
int num=0,tot=0;
void add(int u,int v){
    s[++tot]={u,v,head[u]};
    head[u]=tot;
    s[++tot]={v,u,head[v]};
    head[v]=tot;
}
void dfs(int node,int fa){
    dep[node]=dep[fa]+1;
    id[node]=++num;
    yuan[num]=node;
    dp[node][0]=fa;
    for(int i=1;(1<<i)<=dep[node];++i){
        dp[node][i]=dp[dp[node][i-1]][i-1];
    }
    for(int i=head[node];~i;i=s[i].net){
        if(s[i].to==fa)continue;
        dfs(s[i].to,node);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    int tem=dep[x]-dep[y];
    for(int j=0;tem;++j){
        if(tem&1)x=dp[x][j];
        tem>>=1;
    }
    if(x==y)return x;
    for(int j=24;j>=0;--j){
        if(dp[x][j]!=dp[y][j]){
            x=dp[x][j];
            y=dp[y][j];
        }
    }
    return dp[x][0];
}
int dis(int a,int b){
    return dep[a]+dep[b]-2*dep[lca(a,b)];
}
////////////////////////////////////////////////////////////////////////
int main(){
    memset(head,-1,sizeof(head));
    int n=gn();
    for(int i=1;i<n;++i){
        int u=gn(),v=gn();
        add(u,v);
    }
    dfs(1,0);
    int k=gn();
    for(int i=1;i<=k;++i){
        int num=gn();
        hight[i]=gn();
        a[i].pb(id[hight[i]]);
        for(int j=1;j<num;++j){
            int m=gn();
            hight[i]=lca(hight[i],m);
            a[i].pb(id[m]);
        }
        sort(all(a[i]));
    }
    int q=gn();
    while(q--){
        int city=gn(),control=gn();
        int top;
        for(int j=1;j<=control;++j){
            bang[j]=gn();
            if(j==1)top=hight[bang[j]];
            else top=lca(top,hight[bang[j]]);
        }
        int own=lca(top,city);
        if(top!=own){
            //cout<<top<<" "<<city<<endl;
            printf("%d\n",dis(top,city));
        }
        else{
            int ans=0x3f3f3f3f;
            for(int i=1;i<=control;++i){
                auto it=lower_bound(all(a[bang[i]]),id[city]);
                if(it!=a[bang[i]].end()){
                    ans=min(ans,dis(city,lca(city,yuan[*it])));
                }
                if(it!=a[bang[i]].begin()){
                    ans=min(ans,dis(city,lca(city,yuan[*prev(it)])));
                }
            }
            printf("%d\n",ans);
        }

    }
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/

Alliances

题目描述

输入描述:

输出描述:

题解

Part One：前置理解

Part Two：正题

代码