BZOJ 3572 - 世界树

题目 虚树

题意

  给定一棵树, 多组询问, 求每个点占据的点的数量.
  $1\le N,M\le 3\times 10^5$

分析

  对于每组询问, 很明显先构造出虚树, 并求出到 每一个点到占领它的点的最短距离, 以及 占领它的点的编号.
  我们将 不在虚树边上的点 放在 虚树的点上 , 在虚树边上的点 放在 虚树的边上 , 分开考虑 虚树的边 以及 虚树的点 的贡献.
  虚树的点: 我们只要求出每个虚树的点上有多少个实际的点即可. 这可以轻易地统计.
  虚树的边: 我们找到这一条边的中点, 将中点以上的归在 $father$ , 将中点以下的归在 $current$ .

一个经典的模型

问题描述:

  已知 $AC=x,AE=y,CD=z$, $B$ 为 $ED$ 的中点, 求 $AB$ 的距离.

分析:
  假设 $AE=y=0$ , 即 $A$ 与 $E$ 重合, 考虑简化版的问题.
  很明显有 $AB=\frac{y+z}{2}$ .

  假设 $CD=z=0$ , 即 $C$ 与 $D$ 重合.
  假设 $A$ 和 $C$ 的速度均为 $1$ 个单位每秒, 那么 $A$ 在 $C$ 出发 $y$ 秒后出发, 此时 $A$ 和 $C$ 走的距离相同, 而总距离是 $y-x$ , 所以 $AB=\frac{y-x}{2}$ .

  发现二者可以合并.
  即 $AB=\frac{y-x+z}{2}$ . 这个结论是很有用的, 当 $AE$ 为负数, 即 $E$ 在 $A$ 的右边时, 结论依然成立.

实现

虚树的构建:
  虚树需要维护的信息: t[N],tot, fa[N] .

int cmp(int i,int j) { return dfn[i]<dfn[j]; }
void Virtual(void) {
    sort(h+1,h+m+1,cmp);
    F(i,1,m) {
        int now=h[i];
        if (top==0)
            fa[ s[++top]=t[++tot]=now ]=0;
        else {
            int x=LCA(s[top],now);
            for (;dep[s[top]]>dep[x];s[top--]=0)
                if (dep[s[top-1]]<=dep[x]) fa[s[top]]=x;
            if (x!=s[top])
                fa[ s[top+1]=t[++tot]=x ]=s[top]; top++;
            fa[ s[++top]=t[++tot]=now ]=x;
        }
    }
}

中间变量:
  如果我们进行了重标号, 然后枚举的是标号, 那么每次考虑设中间变量, 表示重标号的原编号.
  这样写起来会简洁很多.

F(i,1,tot) {
    int x=t[i]; ans[pos[near[x].S]]+=w[x];
}

树上倍增:
  树上倍增可以支持:
    1. 求LCA
    2. 一个点向上跳若干步
    3. 一个点跳到深度为 $d$ 的祖先
  本题就使用了3, 我第一次写.

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define P(i,a,b) for (int i=(a);i>=(b);i--)
#define L first
#define S second
const int N=300005;
int n; vector<int> g[N];
int siz[N];
int dfn[N],ind;
int c,dep[N],pre[20][N];
int q;
int m,h[N],pos[N],ans[N];
int t[N],tot,fa[N];
int s[N],top;
int w[N];
pair<int,int> near[N];
int rd(void) {
    int x=0,f=1; char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
void Prework(int x) {
    siz[x]=1; dfn[x]=++ind;
    for (vector<int>::iterator v=g[x].begin();v!=g[x].end();v++)
        if (pre[0][x]!=*v) {
            dep[*v]=dep[x]+1; pre[0][*v]=x;
            Prework(*v);
            siz[x]+=siz[*v];
        }
}
int LCA(int x,int y) {
    if (dep[x]<dep[y]) swap(x,y);
    P(i,c,0) if (dep[pre[i][x]]>=dep[y]) x=pre[i][x];
    if (x==y) return x;
    P(i,c,0) if (pre[i][x]!=pre[i][y]) x=pre[i][x],y=pre[i][y];
    return pre[0][x];
}
int Skip(int x,int d) { P(i,c,0) if (dep[pre[i][x]]>=d) x=pre[i][x]; return x; }
int cmp(int i,int j) { return dfn[i]<dfn[j]; }
void Virtual(void) {
    sort(h+1,h+m+1,cmp);
    F(i,1,m) {
        int now=h[i];
        if (top==0) {
            fa[ s[++top]=t[++tot]=now ]=0;
            near[now]=make_pair(0,now);
            w[now]=siz[now];
        }
        else {
            int x=LCA(s[top],now);
            for (;dep[s[top]]>dep[x];s[top--]=0)
                if (dep[s[top-1]]<=dep[x]) fa[s[top]]=x;
            if (x!=s[top]) {
                fa[ s[top+1]=t[++tot]=x ]=s[top]; top++;
                near[x]=make_pair(~0u>>2,0);
                w[x]=siz[x];
            }
            fa[ s[++top]=t[++tot]=now ]=x;
            near[now]=make_pair(0,now);
            w[now]=siz[now];
        }
    }
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
    #endif
    n=rd(); F(i,1,n-1) { int x=rd(),y=rd(); g[x].push_back(y); g[y].push_back(x); }
    c=(int)log2(n); dep[1]=1; pre[0][1]=1;
    Prework(1);
    F(i,1,c) F(j,1,n) pre[i][j]=pre[i-1][pre[i-1][j]];
    q=rd();
    F(cas,1,q) {
        m=rd(); F(i,1,m) h[i]=rd(),pos[h[i]]=i;
        Virtual();
        sort(t+1,t+tot+1,cmp);
        P(i,tot,2) {
            int x=t[i],f=fa[x];
            near[f]=min(near[f],make_pair(near[x].L+(dep[x]-dep[f]),near[x].S));
        }
        F(i,2,tot) {
            int x=t[i],f=fa[x];
            near[x]=min(near[x],make_pair(near[f].L+(dep[x]-dep[f]),near[f].S));
        }
        F(i,1,tot) {
            int x=t[i],f=fa[x],d=dep[x]-dep[f];
            if (i==1) ans[pos[near[x].S]]+=n-siz[x];
            else {
                int nx=Skip(x,dep[f]+1),sum=siz[nx]-siz[x]; w[f]-=siz[nx];
                if (near[x].S==near[f].S)
                    ans[pos[near[x].S]]+=sum;
                else {
                    int M=dep[x]-(d-near[x].L+near[f].L)/2;
                    if ( (d-near[x].L+near[f].L)%2==0 && near[f].S<near[x].S ) M++;
                    int nx2=Skip(x,M); int sum2=siz[nx2]-siz[x];
                    ans[pos[near[x].S]]+=sum2;
                    ans[pos[near[f].S]]+=sum-sum2;
                }
            }
        }
        F(i,1,tot) {
            int x=t[i]; ans[pos[near[x].S]]+=w[x];
        }
        F(i,1,m) printf("%d ",ans[i]); printf("\n");
        F(i,1,tot) near[t[i]]=make_pair(0,0);
        F(i,1,tot) w[t[i]]=0;
        while (top>0) s[top--]=0;
        F(i,1,tot) fa[t[i]]=0; F(i,1,tot) t[i]=0; tot=0;
        F(i,1,m) pos[h[i]]=0; F(i,1,m) h[i]=ans[i]=0; m=0;
    }
    return 0;
}