title

BZOJ 3572

LUOGU 3233

Description

世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。
世界树的形态可以用一个数学模型来描述：世界树中有n个种族，种族的编号分别从1到n，分别生活在编号为1到n的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连，道路的长度为1。保证连接的方式会形成一棵树结构，即所有的聚居地之间可以互相到达，并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度；例如，若聚居地a和b之间有道路，b和c之间有道路，因为每条道路长度为1而且又不可能出现环，所卧a与c之间的距离为2。
出于对公平的考虑，第i年，世界树的国王需要授权m[i]个种族的聚居地为临时议事处。对于某个种族x（x为种族的编号），如果距离该种族最近的临时议事处为y（y为议事处所在聚居地的编号），则种族x将接受y议事处的管辖（如果有多个临时议事处到该聚居地的距离一样，则y为其中编号最小的临时议事处）。
现在国王想知道，在q年的时间里，每一年完成授权后，当年每个临时议事处将会管理多少个种族（议事处所在的聚居地也将接受该议事处管理）。 现在这个任务交给了以智慧著称的灵长类的你：程序猿。请帮国王完成这个任务吧。

Input

第一行为一个正整数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]]，表示被授权为临时议事处的聚居地编号（保证互不相同）。

Output

输出包含q行，第i行为m[i]个整数，该行的第j(j=1，2…，，m[i])个数表示第i年被授权的聚居地h[j]的临时议事处管理的种族个数。

Sample Input

10
21
32
43
54
61
73
83
94
10 1
5
2
61
5
27369
1
8
4
87103
5
29358

Sample Output

19
31411
10
1135
41311

HINT

N<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000

analysis

参考资料：hzwer。

每一次询问建一颗虚树，这是毋庸置疑的。

然后我们在虚树上面 \(dfs\) 一遍，得到每个点属于（跟从）那个节点。所以之后只需要再统计不在虚树上面的点就好了。

考虑虚树上的一条边：

1. 如果两个端点都属于一个节点，那么只需要再加上两点之间未在虚树上的点即可。
2. 如果两个端点不属于一个节点，那么中间会有分界点，可以倍增地找出这个分界点 \(mid\)，，然后两边分别计算贡献即可。（假设端点为 \(a\) 和 \(b\)，\(b\) 路径上 \(a\) 的第一个儿子为 \(x\)，那么对 \(a\) 的贡献是 \(siz[x]-siz[mid]\)，对 \(b\) 的贡献是 \(siz[mid]-siz[b]\)）
3. 注意我还需要记一个 \(g\) 数组，表示未在上述统计到的节点数，因为有一些点没有在任何一次讨论中被考虑，那么显然将会与他们在虚树上的父亲节点属于同一节点，只要把初值设为 \(siz[x]\)，每次在上面讨论一次，就把讨论的部分删掉即可。

code

#include<bits/stdc++.h>

const int maxn=3e5+10;

namespace IO
{
    char buf[1<<15],*fs,*ft;
    inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
    template<typename T>inline void read(T &x)
    {
        x=0;
        T f=1, ch=getchar();
        while (!isdigit(ch) && ch^'-') ch=getchar();
        if (ch=='-') f=-1, ch=getchar();
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
        x*=f;
    }

    char Out[1<<24],*fe=Out;
    inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
    template<typename T>inline void write(T x,char str)
    {
        if (!x) *fe++=48;
        if (x<0) *fe++='-', x=-x;
        T num=0, ch[20];
        while (x) ch[++num]=x%10+48, x/=10;
        while (num) *fe++=ch[num--];
        *fe++=str;
    }
}

using IO::read;
using IO::write;

struct Graph
{
    int ver[maxn<<1],Next[maxn<<1],head[maxn],len;
    inline void add(int x,int y)
    {
        ver[++len]=y,Next[len]=head[x],head[x]=len;
    }
}A, T;

namespace Virtual
{
    int dfn[maxn],id;
    int siz[maxn],dep[maxn],f[maxn][21];
    inline void dfs(int x)
    {
        dfn[x]=++id;
        siz[x]=1;
        for (int i=1; i<=20; ++i) f[x][i]=f[f[x][i-1]][i-1];
        for (int i=A.head[x]; i; i=A.Next[i])
        {
            int y=A.ver[i];
            if (y==f[x][0]) continue;
            f[y][0]=x;
            dep[y]=dep[x]+1;
            dfs(y);
            siz[x]+=siz[y];
        }
    }

    inline int LCA(int x,int y)
    {
        if (dep[x]>dep[y]) std::swap(x,y);
        for (int i=20; i>=0; --i)
            if (dep[y]-(1<<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];
    }

    inline bool cmp(int a,int b)
    {
        return dfn[a]<dfn[b];
    }

    int Stack[maxn<<1],top;
    inline void insert(int x)
    {
        if (top==1) { Stack[++top]=x; return ; }
        int lca=LCA(Stack[top],x);
        while (dfn[Stack[top-1]]>=dfn[lca] && top>1)
        {
            T.add(Stack[top-1],Stack[top]), --top;
        }
        if (lca!=Stack[top]) T.add(lca,Stack[top]), Stack[top]=lca;
        Stack[++top]=x;
    }

    typedef int iarr[maxn];
    iarr s,dist,bel,ans,c;
    inline void build(int *c,int k)
    {
        std::sort(c+1,c+k+1,cmp);
        T.len=0, Stack[top=1]=1;
        int st;
        if (c[1]^1) st=1;
        else st=2;
        for (int i=st; i<=k; ++i) insert(c[i]);
        while (top>1) T.add(Stack[top-1],Stack[top]),--top;
    }

    inline int Dis(int x,int y)
    {
        return dep[x]+dep[y]-(dep[LCA(x,y)]<<1);
    }

    int cnt;
    inline void calc1(int x)
    {
        c[++cnt]=x, s[x]=siz[x];
        for (int i=T.head[x]; i; i=T.Next[i])
        {
            int y=T.ver[i];
            calc1(y);
            if (!bel[y]) continue;
            if (!bel[x]) { bel[x]=bel[y]; continue; }
            int d1=Dis(bel[y],x),d2=Dis(bel[x],x);
            if ( (d1==d2 && bel[y]<bel[x]) || d1<d2) bel[x]=bel[y];
        }
    }

    inline void calc2(int x)
    {
        for (int i=T.head[x]; i; i=T.Next[i])
        {
            int y=T.ver[i];
            if (!bel[y]) { bel[y]=bel[x]; continue; }
            int d1=Dis(bel[x],y),d2=Dis(bel[y],y);
            if ( (d1==d2 && bel[y]>bel[x]) || d1<d2) bel[y]=bel[x];
            calc2(y);
        }
    }

    inline void solve(int a,int b)
    {
        int x=b,mid=b;
        for (int i=20; i>=0; --i)
            if (dep[x]-(1<<i)>dep[a]) x=f[x][i];
        s[a]-=siz[x];
        if (bel[a]==bel[b])
        {
            ans[bel[a]]+=siz[x]-siz[b];
            return ;
        }
        for (int i=20; i>=0; --i)
        {
            int nxt=f[mid][i];
            if (dep[nxt]<=dep[a]) continue;
            int d1=Dis(bel[a],nxt),d2=Dis(bel[b],nxt);
            if (d1>d2 || (d1==d2 && bel[b]<bel[a])) mid=nxt;
        }
        ans[bel[a]]+=siz[x]-siz[mid];
        ans[bel[b]]+=siz[mid]-siz[b];
    }

    inline void query()
    {
        for (int x=1; x<=cnt; ++x)
            for (int i=T.head[c[x]]; i; i=T.Next[i])
            {
                int y=T.ver[i];
                solve(c[x],y);
            }
        for (int i=1; i<=cnt; ++i) ans[bel[c[i]]]+=s[c[i]];
    }

    inline void Clear()
    {
        for (int i=1; i<=cnt; ++i) ans[c[i]]=bel[c[i]]=T.head[c[i]]=s[c[i]]=0;
        cnt=top=0;
    }
}

using Virtual::dfs;
using Virtual::build;
using Virtual::calc1;
using Virtual::calc2;
using Virtual::query;
using Virtual::Clear;
using Virtual::bel;
using Virtual::ans;

int a[maxn],b[maxn];
int main()
{
    int n;read(n);
    for (int i=1,x,y; i<n; ++i) read(x),read(y),A.add(x,y),A.add(y,x);
    dfs(1);
    int m;read(m);
    while (m--)
    {
        int k;read(k);
        for (int i=1; i<=k; ++i) read(b[i]),a[i]=b[i];
        for (int i=1; i<=k; ++i) bel[a[i]]=a[i];
        build(a,k);
        calc1(1);
        calc2(1);
        query();
        for (int i=1; i<=k; ++i) write(ans[b[i]],i==k ? '\n' : ' ');
        Clear();
    }
    IO::flush();
    return 0;
}

BZOJ 3572: [Hnoi2014]世界树 虚树Dp

原文：https://www.cnblogs.com/G-hsm/p/11386104.html