列表

详情

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

输出描述

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

示例1

输入: 

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

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 2552ms, 内存消耗: 110108K, 提交时间: 2023-04-19 19:23:51 

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+50,M=20;
vector<int>g[N],q[N];
vector<int>x;
int f[N][M],dep[N],dfn[N],id,top[N];
void dfs(int u,int fa)
{
    dfn[u]=++id;dep[u]+=dep[fa]+1;
    f[u][0]=fa;for(int i=1;i<20;i++)    f[u][i]=f[f[u][i-1]][i-1];
    for(int v:g[u])
        if(v!=fa)    dfs(v,u);
}

int lca(int u,int v)
{
    if(dep[v]>dep[u])    swap(u,v);//假定u是dep大的.
    for(int i=19;i>=0;i--)
    {
        if(dep[f[u][i]]>=dep[v])    u=f[u][i];
    }if(u==v)    return v;
    for(int i=19;i>=0;i--)
    {
        if(f[u][i]!=f[v][i])    u=f[u][i],v=f[v][i];
    }return f[u][0];
}

int dis(int u,int v)    {return dep[u]+dep[v]-2*dep[lca(u,v)];}
bool cmp(int a,int b)    {return dfn[a]<dfn[b];}

int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }dfs(1,1);int t;scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        int u,v;scanf("%d",&u);
        for(int j=0;j<u;j++)
        {
            scanf("%d",&v);q[i].push_back(v);
            if(j==0)    top[i]=v;
            else        top[i]=lca(top[i],v);
        }sort(q[i].begin(),q[i].end(),cmp);
    }int Q;scanf("%d",&Q);
    while(Q--)
    {
        x.clear();int V,LCA;scanf("%d",&V);int u,v;scanf("%d",&u);
        for(int i=0;i<u;i++)
        {
            scanf("%d",&v);x.push_back(v);
            if(i==0)    LCA=top[v];
            else        LCA=lca(LCA,top[v]);
        }if(LCA!=lca(LCA,V))    printf("%d\n",dis(V,LCA));
        else
        {
            int ans=2e9;
            for(int e:x)
            {
                int sz=q[e].size();int pos=sz,r=sz-1,l=0;
                while(l<=r)
                {
                    int mid=(l+r)>>1;
                    if(dfn[q[e][mid]]>=dfn[V])    pos=mid,r=mid-1;
                    else                          l=mid+1;
                }
                if(pos!=0)    ans=min(ans,dis(V,lca(q[e][pos-1],V)));
                if(pos!=sz)   ans=min(ans,dis(V,lca(q[e][pos],V)));
            }printf("%d\n",ans);
        }
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1963ms, 内存消耗: 99960K, 提交时间: 2020-08-14 00:51:03 

#include<bits/stdc++.h>
using namespace std;

vector<int>R[500005],T[500005];
vector<int>::iterator it;
int a[500005],Dep[500005]={0},F[500005][20],dfn[500005],top[500005],ID[500005],t,tot=0;
void DFS(int x,int fa)
{
    int i,j,k;
    dfn[x]=++tot,ID[tot]=x;
    for(i=0;i<R[x].size();i++)
    {
        j=R[x][i];
        if(j==fa)continue;
        Dep[j]=Dep[x]+1,F[j][0]=x;
        for(k=1;k<=t;k++)F[j][k]=F[F[j][k-1]][k-1];
        DFS(j,x);
    }
}
int lca(int x,int y)
{
    int i;
    if(Dep[x]>Dep[y])swap(x,y);
    for(i=t;i>=0;i--)if(Dep[F[y][i]]>=Dep[x])y=F[y][i];
    if(y==x)return x;
    for(i=t;i>=0;i--)if(F[y][i]!=F[x][i])y=F[y][i],x=F[x][i];
    return F[x][0];
}
int main()
{
    int i,j,k,x,s,Top,ans,n,m,q;
	scanf("%d",&n),t=(int)(log(n)/log(2))+1;
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&j,&k);
		R[j].push_back(k),R[k].push_back(j);
	}
	F[1][0]=1,DFS(1,0);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d",&s);
		for(j=1;j<=s;j++)
		{
			scanf("%d",&x);
			T[i].push_back(dfn[x]);
			if(j==1)top[i]=x;
			else top[i]=lca(top[i],x);
		}
		sort(T[i].begin(),T[i].end());
	}
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d%d",&x,&s),ans=1e9;
		for(i=1;i<=s;i++)
		{
			scanf("%d",&a[i]);
			if(i==1)Top=top[a[i]];
			else Top=lca(Top,top[a[i]]);
		}
		if(lca(Top,x)!=Top){printf("%d\n",Dep[Top]+Dep[x]-2*Dep[lca(Top,x)]);continue;}
		for(i=1;i<=s;i++)
		{
			it=lower_bound(T[a[i]].begin(),T[a[i]].end(),dfn[x]);
			if(it!=T[a[i]].end())j=lca(x,ID[*it]),ans=min(ans,Dep[x]-Dep[j]);
			if(it!=T[a[i]].begin())j=lca(x,ID[*(--it)]),ans=min(ans,Dep[x]-Dep[j]);
		}
		printf("%d\n",ans);
	}
	return 0;
}

上一题

© 2024 nowcoder.com