description

题面

data range

\[n\le 300000, q\le 300000,\sum m\le 300000\]

solution

仍然是虚树的题
听说许多大佬把这道题当做模板???
感觉还是挺神的

考虑只有一次询问我们如何做这个\(dp\)
先自底向上\(dp\)找到子树内离每个点最近的标记点
由于实际最近的标记点可能不在子树内，因此还要自顶向下\(dp\)一遍
最后\(for\)每个节点\(ans++\)就可以了
这样的复杂度是\(O(n)\)

建出虚树后，我们仍然可以通过两遍\(O(k)\)的\(dp\)找到每个虚树节点的最近标记点
之后我们要分配每一条连接两个虚树节点的链
考虑到虚树中两个成父子关系的节点在原树上一定呈祖先关系，所以可以直接使用倍增暴跳
统计答案时几个子树\(size\)减一下分配给两边就可以了

复杂度?反正一个\(log\)

code

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FILE "a"
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int mod=998244353;
const int N=500010;
const dd pi=acos(-1);
const int inf=2147483647;
const ll INF=1e18+1;
const ll P=100000;
il ll read(){
    RG ll data=0,w=1;RG char ch=getchar();
    while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘))ch=getchar();
    if(ch==‘-‘)w=-1,ch=getchar();
    while(ch<=‘9‘&&ch>=‘0‘)data=data*10+ch-48,ch=getchar();
    return data*w;
}

il void file(){
    srand(time(NULL)+rand());
    freopen("1.in","r",stdin);
    freopen(FILE".out","w",stdout);
}

int n,m,q,k;
int head[N],nxt[N<<1],to[N<<1],cnt;
int fa[20][N],sz[N],son[N],dep[N],top[N],low[N],dfn[N],tot;
void dfs1(int u,int ff){
    fa[0][u]=ff;sz[u]=1;dep[u]=dep[ff]+1;
    for(RG int i=1;fa[i-1][fa[i-1][u]];i++)
        fa[i][u]=fa[i-1][fa[i-1][u]];
    for(RG int i=head[u];i;i=nxt[i]){
        RG int v=to[i];if(v==ff)continue;
        dfs1(v,u);sz[u]+=sz[v];
        if(sz[son[u]]<sz[v])son[u]=v;
    }
}
void dfs2(int u,int tp){
    dfn[u]=++tot;top[u]=tp;if(son[u])dfs2(son[u],tp);
    for(RG int i=head[u];i;i=nxt[i]){
        RG int v=to[i];if(v==fa[0][u]||v==son[u])continue;
        dfs2(v,v);
    }
    low[u]=++tot;
}
il int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[0][top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
il int jump(int u,int d){
    for(RG int i=0;d;i++)
        if(d&(1<<i)){u=fa[i][u];d^=(1<<i);}
    return u;
}

bool cmp_dfn(int i,int j){return dfn[i]<dfn[j];}
int dhead[N],dnxt[N<<1],dto[N<<1],dcnt;bool mark[N];
int o[N],s[N],cal[N],tp;
il void addedge(int u,int v){
    dto[++dcnt]=v;
    dnxt[dcnt]=dhead[u];
    dhead[u]=dcnt;
}

int mndis[N],mndisnum[N];
void dfs3(int u,int ff){
    if(!mndis[u])mndis[u]=n;
    if(ff){mndis[u]=mndis[ff]+dep[u]-dep[ff];mndisnum[u]=mndisnum[ff];}
    if(mark[u]){mndis[u]=0;mndisnum[u]=u;}
    for(RG int i=dhead[u];i;i=dnxt[i]){
        RG int v=dto[i];dfs3(v,u);
        RG int d=mndis[v]+dep[v]-dep[u];
        if(mndis[u]>d||(mndis[u]==d&&mndisnum[u]>mndisnum[v]))
            mndis[u]=d,mndisnum[u]=mndisnum[v];
    }
}
void dfs4(int u,int ff){
    for(RG int i=dhead[u];i;i=dnxt[i]){
        RG int v=dto[i];
        RG int d=mndis[u]+dep[v]-dep[u];
        if(mndis[v]>d||(mndis[v]==d&&mndisnum[v]>mndisnum[u]))
            mndis[v]=d,mndisnum[v]=mndisnum[u];
        dfs4(v,u);
    }
}

int own[N];
void solve(int u){
    own[mndisnum[u]]+=sz[u];
    for(RG int i=dhead[u];i;i=dnxt[i]){
        RG int v=dto[i],x=jump(v,dep[v]-dep[u]-1);solve(v);
        if(mndisnum[u]==mndisnum[v])own[mndisnum[u]]+=sz[x]-sz[v];
        else if(dep[v]!=dep[u]+1){
            RG int y=jump(v,(dep[v]-dep[u]+mndis[u]-mndis[v]-1)/2);         
            if(((dep[v]-dep[u]+mndis[u]-mndis[v]-1)&1)&&(dep[fa[0][y]]-dep[u]+mndis[u]==dep[v]-dep[fa[0][y]]+mndis[v])&&mndisnum[v]<mndisnum[u])
                y=fa[0][y];
            own[mndisnum[u]]+=sz[x]-sz[y];          
            own[mndisnum[v]]+=sz[y]-sz[v];
            assert(own[mndisnum[u]]>=0);
        }
        own[mndisnum[u]]-=sz[x];
        assert(own[mndisnum[u]]>=0);
    }
}

int main()
{
    n=read();
    for(RG int i=1,u,v;i<n;i++){
        u=read();v=read();
        to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
        to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
    }
    dfs1(1,0);dfs2(1,1);
    
    q=read();
    for(RG int i=1;i<=q;i++){
        m=read();tp=k=dcnt=0;
        for(RG int j=1;j<=m;j++)o[j]=s[++k]=read(),mark[s[k]]=1;
        sort(s+1,s+k+1,cmp_dfn);
        for(RG int j=1;j<m;j++)s[++k]=lca(s[j],s[j+1]);s[++k]=1;
        sort(s+1,s+k+1,cmp_dfn);k=unique(s+1,s+k+1)-s-1;
        for(RG int j=1;j<=k;j++){
            while(tp&&low[cal[tp]]<dfn[s[j]])tp--;
            if(tp)addedge(cal[tp],s[j]);cal[++tp]=s[j];
        }
        dfs3(1,0);dfs4(1,0);solve(1);
        for(RG int j=1;j<=m;j++)printf("%d ",own[o[j]]),own[o[j]]=0;
        puts("");
        for(RG int j=1;j<=k;j++)
            dhead[s[j]]=mark[s[j]]=mndis[s[j]]=mndisnum[s[j]]=0;
    }
    return 0;
}

[HNOI2014]世界树

原文：https://www.cnblogs.com/cjfdf/p/9489570.html