svisor - 动态点分治 - 虚树

题目大意：
给你一颗树，多次询问，每次询问给定k个关键点以及每个点的半径，问这k个点能够覆盖到的点的并集的大小。
题解：
考虑k=1怎么做：直接动态点分治即可。
考虑建出虚树，重新更新每个点的半径使得不存在两个点，其中一个延申到另一个时，半径仍然大于另一个。
考虑我们已经处理虚树上x的前若干棵子树的点，能够覆盖到的点的并集，现在新增一颗子树y并进去，那么要减去新增后重复计算的点，方法是虚树上(x,y)这条边对应的路径上找到一个点z（有可能在边的中点上），使得x和y在这个点的影响相同（即能够扩展出相同的距离r），减掉z这个点距离r的答案即可。
因为z有可能在边上，所有边拆点即可，用动态点分治维护上述过程。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define lint long long
#define ull unsigned lint
#define db long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define debug(x) cerr<<#x<<\"=\"<<x
#define sp <<\" \"
#define ln <<endl
using namespace std;
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
namespace INPUT_SPACE{
    const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;
    char gc() { if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);return (HD==TL)?EOF:*HD++; }
    inline int inn()
    {
        int x,ch;while((ch=gc())<\'0\'||ch>\'9\');
        x=ch^\'0\';while((ch=gc())>=\'0\'&&ch<=\'9\')
            x=(x<<1)+(x<<3)+(ch^\'0\');return x;
    }
}using INPUT_SPACE::inn;
namespace OUTPUT_SPACE{
    char ss[50010*12],tt[30];int ssl,ttl;
    inline int print(int x)
    {
        if(!x) ss[++ssl]=\'0\';for(ttl=0;x;x/=10) tt[++ttl]=char(x%10+\'0\');
        for(;ttl;ttl--) ss[++ssl]=tt[ttl];return ss[++ssl]=\'\\n\';
    }
    inline int Flush() { return fwrite(ss+1,sizeof(char),ssl,stdout),ssl=0,0; }
}using OUTPUT_SPACE::print;using OUTPUT_SPACE::Flush;
const int N=100010,Q=50010,LOG=20;
inline int gabs(int x) { return x<0?-x:x; }
struct edges{
    int to,pre;
}e[N<<1];int h[N],etop,dfn[N],tms[N],dfc,dpt[N],val[N],Ans[Q];
inline int add_edge(int u,int v) { return e[++etop].to=v,e[etop].pre=h[u],h[u]=etop; }
namespace LCA_space{
    int fir[N],f[N<<1][LOG],len,Log[N<<1];
    inline int Mymax(int x,int y) { return dpt[x]<dpt[y]?x:y; }
    int dfs(int x,int fa)
    {
        f[fir[x]=++len][0]=x,tms[dfn[x]=++dfc]=x,dpt[x]=dpt[fa]+1;
        for(int i=h[x],y;i;i=e[i].pre) if((y=e[i].to)^fa) dfs(y,x),f[++len][0]=x;
        return 0;
    }
    inline int prelude()
    {
        len=0,dfc=0,dpt[0]=0,dfs(1,0);
        for(int j=1;(1<<j)<=len;j++)
            for(int i=1;i+(1<<j)-1<=len;i++)
                f[i][j]=Mymax(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        rep(i,2,len) Log[i]=Log[i>>1]+1;return 0;
    }
    inline int LCA(int x,int y)
    {
        x=fir[x],y=fir[y];if(x>y) swap(x,y);
        int k=Log[y-x+1];return Mymax(f[x][k],f[y-(1<<k)+1][k]);
    }
}using LCA_space::LCA;
namespace PX_space{
    vector<pii> v[N];inline int Ins(pii *a,int n,int id) { rep(i,1,n) v[dfn[a[i].fir]].pb(mp(id,a[i].sec));return 0; }
    inline int solve(vector<pii> *ans,int n) { rep(i,1,n) Rep(j,v[i]) ans[v[i][j].fir].pb(mp(tms[i],v[i][j].sec));return 0; }
}
namespace KDIS_space{
    int dis[LOG][N],fr[LOG][N],mxl[LOG][N],*cnt[LOG][N],vis[N],Lst[N],Lcnt,sz[N],dftd[N],fa[N];
    inline int *NewInt(int n) { int *t=new int[n];memset(t,0,sizeof(int)*n);return t; }
    int dfs(int x,int fa,int z,int d,int dpt)
    {
        dis[d][x]=dpt,fr[d][x]=z,mxl[d][x]=dpt;
        for(int i=h[x],y;i;i=e[i].pre)
            if(!vis[y=e[i].to]&&e[i].to!=fa) mxl[d][x]=max(mxl[d][x],dfs(y,x,z,d,dpt+1));
        return mxl[d][x];
    }
    int getcnt(int x,int fa,int d,int *c1,int *c2)
    {
        c1[d]+=val[x],c2[d]+=val[x];
        for(int i=h[x],y;i;i=e[i].pre)
            if(!vis[y=e[i].to]&&e[i].to!=fa) getcnt(y,x,d+1,c1,c2);
        return 0;
    }
    int getsz(int x,int fa)
    {
        sz[x]=1,Lst[++Lcnt]=x;
        for(int i=h[x],y;i;i=e[i].pre)
            if(!vis[y=e[i].to]&&e[i].to!=fa) sz[x]+=getsz(y,x);
        return sz[x];
    }
    int getrt(int &x)
    {
        for(int i=1,fsz=sz[x],t=fsz;i<=Lcnt;i++)
        {
            int y=Lst[i],ysz=fsz-sz[y];
            for(int j=h[y],z;j;j=e[j].pre)
                if(!vis[z=e[j].to]&&sz[e[j].to]<sz[y]) ysz=max(ysz,sz[z]);
            if(ysz<t) t=ysz,x=y;
        }
        return 0;
    }
    int dfz(int x,int d,int f)
    {
        Lcnt=0,getsz(x,0),getrt(x),vis[x]=1,dftd[x]=d,fa[x]=f;
        for(int i=h[x],y;i;i=e[i].pre) if(!vis[y=e[i].to])
            mxl[d][x]=max(mxl[d][x],dfs(y,x,y,d,1)),cnt[d][y]=NewInt(mxl[d][y]+1);
        cnt[d][x]=NewInt(mxl[d][x]+1),cnt[d][x][0]=val[x];
        for(int i=h[x],y;i;i=e[i].pre) if(!vis[y=e[i].to])
        {
            getcnt(y,x,1,cnt[d][y],cnt[d][x]);
            rep(j,1,mxl[d][y]) cnt[d][y][j]+=cnt[d][y][j-1];
        }
        rep(i,1,mxl[d][x]) cnt[d][x][i]+=cnt[d][x][i-1];
        for(int i=h[x],y;i;i=e[i].pre) if(!vis[y=e[i].to]) dfz(y,d+1,x);
        return 0;
    }
    inline int build() { return dfz(1,0,0); }
    inline int kdis(int x,int k)
    {
        int d=dftd[x],ans=cnt[d][x][min(k,mxl[d][x])];
        for(int i=d-1,y=fa[x],z;i>=0;i--,y=fa[y]) if(k>=dis[i][x])
            z=fr[i][x],ans+=cnt[i][y][min(k-dis[i][x],mxl[i][y])]-cnt[i][z][min(k-dis[i][x],mxl[i][z])];
        return ans;
    }
@font-face {
				font-family: "autolinktags";
				src: url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.woff2") format("woff2"),
				url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.woff") format("woff"),
				url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.ttf") format("truetype");
				font-weight:normal;
				font-style:normal;
			}.tagslink::after { content:"\e613"; margin:2px 0 0 0px; font-size:12px; font-family:"autolinktags"; display:inline-block; vertical-align:top; }