...

Alliances

http://www.nowcoder.com/questionTerminal/5109332dc9b141ad9d4d1a3f862ef901

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

define rep(i,m,n) for(i=m;i<=(int)n;i++)

define inf 0x3f3f3f3f

define mod 998244353

define vi vector

define pb push_back

define mp make_pair

define fi first

define se second

define ll long long

define pi acos(-1.0)

define pii pair<int,int>

define sys system("pause")

define ls (rt<<1)

define rs (rt<<1|1)

define all(x) x.begin(),x.end()

const int maxn=5e5+10;
const int N=2e5+10;
using namespace std;

int n,m,k,t,dfn[maxn],st[maxn],anc[maxn],dep[maxn],fa[20][maxn],tot,cnt,head[maxn];
vector<int> p[maxn];
struct node
{
int to,nxt;
}e[maxn<<1];
void add(int x,int y)
{
e[cnt].to=y;
e[cnt].nxt=head[x];
head[x]=cnt++;
}
set<int>bl[maxn];
void dfs(int x,int y)
{
int i;
dfn[++tot]=x;
st[x]=tot;
dep[x]=dep[y]+1;
for(i=1;fa[i-1][fa[i-1][x]];i++)
{
fa[i][x]=fa[i-1][fa[i-1][x]];
}
for(i=head[x];i!=-1;i=e[i].nxt)
{
int z=e[i].to;
if(z==y)continue;
fa[0][z]=x;
dfs(z,x);
}
}
int lca(int x,int y)
{
int i;
if(dep[x]<dep[y])swap(x,y);
for(i=19;i>=0;i--)if(dep[fa[i][x]]>=dep[y])x=fa[i][x];
if(x==y)return x;
for(i=19;i>=0;i--)
{
if(fa[i][x]!=fa[i][y])
{
x=fa[i][x];
y=fa[i][y];
}
}
return fa[0][x];
}
int main(){
int i,j;
scanf("%d",&n);
rep(i,1,n)head[i]=-1;
rep(i,1,n-1)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
scanf("%d",&m);
rep(i,1,m)
{
scanf("%d",&j);
while(j--)scanf("%d",&k),p[k].pb(i);
}
dfs(1,0);
rep(i,1,n)
{
rep(j,0,p[i].size()-1)
{
if(anc[p[i][j]]==0)anc[p[i][j]]=i;
else anc[p[i][j]]=lca(anc[p[i][j]],i);
bl[p[i][j]].insert(st[i]);
}
}
int q;
scanf("%d",&q);
while(q--)
{
int cap,fa=-1,pr=-1,nt=-1;
scanf("%d",&cap);
scanf("%d",&j);
while(j--)
{
scanf("%d",&k);
auto x=bl[k].lower_bound(st[cap]);
if(x!=bl[k].end())
{
if(nt==-1)nt=x;
else nt=min(nt,
x);
}
if(x!=bl[k].begin()&&(x==bl[k].end()||x>st[cap]))--x;
if(x!=bl[k].end()&&
x<=st[cap])
{
if(pr==-1)pr=x;
else pr=max(pr,
x);
}
if(fa==-1)fa=anc[k];
else fa=lca(anc[k],fa);
}
int x_fa=lca(fa,cap);
if(x_fa==cap||x_fa!=fa)printf("%d\n",dep[fa]+dep[cap]-2*dep[x_fa]);
else
{
int ret1=1e9,ret2=1e9;
if(pr!=-1)pr=dfn[pr],ret1=dep[cap]-dep[lca(pr,cap)];
if(nt!=-1)nt=dfn[nt],ret2=dep[cap]-dep[lca(nt,cap)];
printf("%d\n",min(ret1,ret2));
}
}
return 0;
}</int></int>

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务