题解 P3233 [HNOI2014]世界树

Varuxn · 2021-06-19 11:00:25 · 题解

题目传送门

推销

解题思路

正解当然是虚树了。

首先对于原树以及虚树各开一个结构体存边，这个不用多说。

然后我们先 DFS 一遍，求出各个节点的时间戳，子树大小，深度以及父亲节点，并初始化倍增 LCA 。

对于每一次的操作，我们都建一棵虚树（注意数组的清空），为了方便，我们此后操作的 DFS 都从 1 节点开始，如果 1 节点不是临时议事处，我们也把它给加入到虚树中并做一下标记。

显然，在建虚树之前，要先把所有的临时议事处按照时间戳排序，然后建虚树。

此后没，我们进行两遍 DFS :

• 第一遍：用于更新虚树中所有节点的 dp 以及其所属的临时议事处。

  因为虚树的深度较小的点不一定是临时议事处，而所有的叶子节点一定是临时议事处。

  所以，先遍历到叶子节点，再用叶子节点来更新父亲节点。

• 第二遍：利用所有的虚树中的值进而求出原树中的值。

  1. 如果子树中没有临时议事处，那么这个节点管辖的点数就要加上子树的siz。

  2. 在原树上是一条链，并且两端都是临时议事处，那么直接一半一半分就好了。

  • 注意：此过程也需要更新虚树上点的 dp 值以及所属临时议事处，但是不同与第一次 DFS 的是由父亲节点更新叶子节点。

最后输出时注意判断 1 节点是否是临时议事处就好了。

code

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10,M=N<<1,INF=1e9;
int n,m,Q,tim,s[N],dp[N],g[N],dfn[N],q[N],ans[N],f[N][25],siz[N],dep[N];
int top,sta[N];
bool flag,vis[N];
struct Edge
{
    int tot,head[N],nxt[M],ver[M];
    void add(int x,int y)
    {
        ver[++tot]=y;
        nxt[tot]=head[x];
        head[x]=tot;
    }
}e1,e2;
void dfs(int x,int fat)
{
    f[x][0]=fat;
    siz[x]=1;
    dfn[x]=++tim;
    for(int i=e1.head[x];i;i=e1.nxt[i])
    {
        int to=e1.ver[i];
        if(to==fat)
            continue;
        dep[to]=dep[x]+1;
        dfs(to,x);
        siz[x]+=siz[to];
    }
}
void LCA_init()
{
    dep[1]=1;
    dfs(1,0);
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
            f[j][i]=f[f[j][i-1]][i-1];
}
int LCA_ask(int x,int y)
{
    if(x==y)
        return x;
    if(dep[x]>dep[y])
        swap(x,y);
    for(int i=20;i>=0;i--)
        if(dep[f[y][i]]>=dep[x])
            y=f[y][i];
    if(x==y)
        return x;
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    return f[x][0];
}
bool comp(int x,int y)
{
    return dfn[x]<dfn[y];
}
void build(int x)
{
    if(!top)
    {
        sta[++top]=x;
        return ;
    }
    int lca=LCA_ask(x,sta[top]);
    while(top>1&&dep[lca]<dep[sta[top-1]])
    {
        e2.add(sta[top-1],sta[top]);
        e2.add(sta[top],sta[top-1]);
        top--;
    }
    if(dep[lca]<dep[sta[top]])
    {
        e2.add(lca,sta[top]);
        e2.add(sta[top],lca);
        top--;
    }
    if(!top||sta[top]!=lca)
        sta[++top]=lca;
    sta[++top]=x;
}
void dfs1(int x,int fa)
{
    dp[x]=INF;
    for(int i=e2.head[x];i;i=e2.nxt[i])
    {
        int to=e2.ver[i];
        if(to==fa)
            continue;
        dfs1(to,x);
        int dis=dep[to]-dep[x];
        if(dp[x]>dp[to]+dis)
        {
            g[x]=g[to];
            dp[x]=dp[to]+dis;
        }
        else if(dp[x]==dp[to]+dis)
            g[x]=min(g[x],g[to]);
    }
    if(vis[x])
    {
        dp[x]=0;
        g[x]=x;
    }
}
void work(int x,int y)
{
    int b=y;
    for(int i=20;i>=0;i--)
    {
        int l=dep[y]-dep[f[b][i]]+dp[y],r=dep[f[b][i]]-dep[x]+dp[x];
        if(dep[f[b][i]]>dep[x]&&(l<r||(l==r&&g[y]<g[x])))
            b=f[b][i];
    }
    ans[g[y]]+=siz[b]-siz[y];
    ans[g[x]]-=siz[b];
}
void dfs2(int x,int fa)
{
    for(int i=e2.head[x];i;i=e2.nxt[i])
    {
        int to=e2.ver[i];
        if(to==fa)
            continue;
        int dis=dep[to]-dep[x];
        if(dp[to]>dp[x]+dis)
        {
            g[to]=g[x];
            dp[to]=dp[x]+dis;
        }
        else if(dp[to]==dp[x]+dis)
            g[to]=min(g[to],g[x]);
        work(x,to);
        dfs2(to,x);
    }
    ans[g[x]]+=siz[x];
}
int main()
{
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        e1.add(x,y);
        e1.add(y,x);
    }
    LCA_init();
    scanf("%d",&Q);
    while(Q--)
    {
        flag=top=e2.tot=0;
        memset(vis,false,sizeof(vis));
        memset(e2.head,0,sizeof(e2.head));
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&q[i]);
            vis[q[i]]=true;
            ans[q[i]]=0;
        }
        if(!vis[1])
        {
            flag=true;
            q[++m]=1;
        }
        for(int i=1;i<=m;i++)
            s[i]=q[i];
        sort(s+1,s+m+1,comp);
        for(int i=1;i<=m;i++)
            build(s[i]);
        if(top)
            while(--top)
            {
                e2.add(sta[top],sta[top+1]);
                e2.add(sta[top+1],sta[top]);
            }
        dfs1(1,0);
        dfs2(1,0);
        for(int i=1;i<=m;i++)
            if(q[i]!=1||!flag)
                printf("%d ",ans[q[i]]);
        printf("\n");
    }
    return 0;
}