NC20106. [HNOI2014]世界树
描述
输入描述
第一行为一个正整数n，表示世界树中种族的个数。
接下来n-l行，每行两个正整数x，y，表示x聚居地与y聚居地之间有一条长度为1的双向道路。
接下来一行为一个正整数q，表示国王询问的年数。
接下来q块，每块两行：
第i块的第一行为1个正整数m[i]，表示第i年授权的临时议事处的个数。
第i块的第二行为m[i]个正整数h[l]、h[2]、…、h[m[i]]，表示被授权为临时议事处的聚居地编号（保证互不相同）。
输出描述
输出包含q行，第i行为m[i]个整数，该行的第j(j=1，2…，，m[i])个数表示第i年被授权的聚居地h[j]的临时议事处管理的种族个数。
示例1
输入:
10 2 1 3 2 4 3 5 4 6 1 7 3 8 3 9 4 10 1 5 2 6 1 5 2 7 3 6 9 1 8 4 8 7 10 3 5 2 9 3 5 8
输出:
1 9 3 1 4 1 1 10 1 1 3 5 4 1 3 1 1
C++ 解法, 执行用时: 237ms, 内存消耗: 43052K, 提交时间: 2021-08-16 23:31:23
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
const int inf = 0x3f3f3f3f;
int tot,head[N],n,k,impt[N],h[N],query[N],lg[N],ans[N];
struct Edge
{
int next,to,from;
}edge[N<<1];
void addedge(int from,int to)
{
edge[++tot].next=head[from];
edge[tot].to=to;
head[from]=tot;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
namespace VirtualTree{
int fa[N][20],dfn[N],dep[N],cnt,siz[N];
void pre_dfs(int u,int f,int deep){
fa[u][0]=f,dep[u]=deep,dfn[u]=++cnt,siz[u]=1;
for(int i=1;i<=lg[deep];++i) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(v==f) continue;
pre_dfs(v,u,deep+1);
siz[u]+=siz[v];
}
}
int getlca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=fa[x][lg[dep[x]-dep[y]]-1];
if(x==y) return x;
for(int i=lg[dep[x]]-1;i>=0;i--)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
Edge vedge[N];
int vtot,vhead[N];
void vadd(int from,int to) {
vedge[++vtot].next=vhead[from];
vedge[vtot].to=to;
vedge[vtot].from=from;
vhead[from]=vtot;
}
bool cmp(int x,int y){return dfn[x]<dfn[y];}
int sta[N],top;
void build() {
sort(impt+1,impt+1+k,cmp);
sta[top=1]=1; vtot=0,vhead[1]=0;
for(int i=1;i<=k;++i)
{
if(impt[i]==1) continue;
int lca=getlca(impt[i],sta[top]);
if(lca!=sta[top]){
while(dfn[lca]<dfn[sta[top-1]]) vadd(sta[top-1],sta[top]),--top;
if(dfn[lca]>dfn[sta[top-1]]) vhead[lca]=0,vadd(lca,sta[top]),sta[top]=lca;
else vadd(lca,sta[top--]);
}
vhead[impt[i]]=0,sta[++top]=impt[i];
}
for(int i=1;i<top;++i) vadd(sta[i],sta[i+1]);
}
int dp[N],g[N];//dp记录距离关键点最小距离，g记录对应关键点编号
void cal(int x,int y)
{
int p=y,q=y;
for(int i=lg[dep[p]];i>=0;--i) if(dep[fa[p][i]]>dep[x]) p=fa[p][i];
ans[g[x]]-=siz[p];
for(int i=lg[dep[q]];i>=0;--i) {
int len1=dep[y]-dep[fa[q][i]]+dp[y],len2=dep[fa[q][i]]-dep[x]+dp[x];
if(dep[fa[q][i]]>dep[x]&&(len1<len2||(len1==len2&&g[y]<g[x]))) q=fa[q][i];
}
ans[g[y]]+=siz[q]-siz[y],ans[g[x]]+=siz[p]-siz[q];
}
void dfs1(int u){
dp[u]=inf;
for(int i=vhead[u];i;i=vedge[i].next){
int v=vedge[i].to,dis=dep[v]-dep[u];
dfs1(v);
if(dp[v]+dis<dp[u]) dp[u]=dp[v]+dis,g[u]=g[v];
else if(dp[v]+dis==dp[u]) g[u]=min(g[u],g[v]);
}
if(query[u]) dp[u]=0,g[u]=u,query[u]=0;
}
void dfs2(int u){
for(int i=vhead[u];i;i=vedge[i].next){
int v=vedge[i].to,dis=dep[v]-dep[u];
if(dp[u]+dis<dp[v]) dp[v]=dp[u]+dis,g[v]=g[u];
else if(dp[u]+dis==dp[v]) g[v]=min(g[v],g[u]);
cal(u,v);
dfs2(v);
}
ans[g[u]]+=siz[u];
}
void solve()
{
k=read();
for(int i=1;i<=k;++i)
impt[i]=read(),query[impt[i]]=1,ans[impt[i]]=0,h[i]=impt[i];
build();
dfs1(1);
dfs2(1);
for(int i=1;i<=k;++i) printf("%d ",ans[h[i]]);
puts("");
}
}
int main()
{
n=read();
for(int i=1,x,y;i<n;++i){
x=read(),y=read();
lg[i]=lg[i-1]+(1<<lg[i-1]==i);
addedge(x,y),addedge(y,x);
}
lg[n]=lg[n-1]+(1<<lg[n-1]==n);
VirtualTree::pre_dfs(1,0,1);
int q=read();
while(q--) VirtualTree::solve();
}
C++14(g++5.4) 解法, 执行用时: 556ms, 内存消耗: 45904K, 提交时间: 2019-04-17 07:57:49
#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define REP(u) for(int i=hd[u],v=e[i].v;i;i=e[i].n,v=e[i].v)
#define REQ(u) for(int i=Hd[u],v=E[i].v;i;i=E[i].n,v=E[i].v)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define p pair<int,int>
const int N=1e6+5;
const int INF=1e7;
struct edge{int n,v;}e[N],E[N];
int n,m,T,u,v,ti,top,top2,tot,rt;
int a[N],b[N],df[N],sz[N],d[N],tn[N],up[N];
int f[N][25],zhan[N],Hd[N],hd[N],ans[N],A[N];
p g[N];
void add(int u,int v){e[++top]=(edge){hd[u],v};hd[u]=top;}
void Add(int u,int v){E[++top2]=(edge){Hd[u],v};Hd[u]=top2;}
void dfs0(int u){
df[u]=++ti;sz[u]=1;
REP(u)if(v!=f[u][0])
f[v][0]=u,d[v]=d[u]+1,dfs0(v),sz[u]+=sz[v];
}
void dfs1(int u){
if(b[u]==1) g[u]=p(0,u);else g[u]=p(INF,0);
REQ(u) dfs1(v),g[u]=min(g[u],p(g[v].fr+d[v]-d[u],g[v].sc));
}
void dfs2(int u,int D,int x)
{
if(p(D,x)<g[u]) g[u]=p(D,x);else D=g[u].fr,x=g[u].sc;
REQ(u) dfs2(v,D+d[v]-d[u],x);
}
void dfs3(int u)
{
tn[u]=g[u].sc;
ans[tn[u]]+=sz[u];
REQ(u){
int x=v;
ROF(j,20,0) if(f[x][j] && d[f[x][j]]>d[u]) x=f[x][j];
ans[tn[u]]-=sz[up[v]=x];dfs3(v);
}
}
void dfs4(int u)
{
REQ(u){
int x=up[v],y=v,H;
if(tn[u]==tn[v]) ans[tn[u]]+=sz[x]-sz[v];
else{
H=d[tn[v]]+d[u]-g[u].fr;
H=H&1?H+1>>1:(tn[v]<tn[u]?H>>1:(H>>1)+1);
ROF(j,20,0) if(f[y][j] && d[f[y][j]]>=H) y=f[y][j];
ans[tn[v]]+=sz[y]-sz[v];
ans[tn[u]]+=sz[x]-sz[y];
}dfs4(v);
}
}
void dfs5(int u){up[u]=tn[u]=0;REQ(u) dfs5(v);Hd[u]=0;}
int lca(int u,int v)
{
if(d[u]<d[v]) swap(u,v);
ROF(j,20,0) if(d[f[u][j]]>=d[v] && f[u][j]) u=f[u][j];
if(u==v) return u;
ROF(j,20,0) if(f[u][j]!=f[v][j] && f[u][j]) u=f[u][j],v=f[v][j];
return f[u][0];
}
bool cmp(int x,int y){return df[x]<df[y];}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs0(1);
for(int j=1;j<=20;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
scanf("%d",&T);
while(T--)
{
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
A[i]=a[i];
b[a[i]]=1;
}
sort(a+1,a+m+1,cmp);
zhan[tot=1]=a[1];
FOR(i,2,m){
int x=a[i],y=lca(x,zhan[tot]);
while(tot>1&&d[y]<=d[zhan[tot-1]])
Add(zhan[tot],zhan[tot--]);
if(zhan[tot]!=y)
{
Add(y,zhan[tot]);
zhan[tot]=y;
}
zhan[++tot]=x;
}
while(tot>1) Add(zhan[tot],zhan[tot--]);
rt=zhan[1];
dfs1(rt);
dfs2(rt,g[rt].fr,g[rt].sc);
dfs3(rt);
dfs4(rt);
ans[tn[rt]]+=sz[1]-sz[rt];
for(int i=1;i<=m;i++)
printf("%d ",ans[A[i]]);
puts("");
dfs5(rt);
for(int i=1;i<=m;i++)b[a[i]]=ans[a[i]]=0;
top2=0;
}
return 0;
}