bzoj3572[HNOI2014]世界树

只说一下大概做法吧，我这个做法好难写(或许有的地方是可以简便的做到的)，首先建虚树，把虚树上的"议事处"叫做黑点，其他点叫做白点。
对于每个白点算出最近的黑点以及到它的距离(这个我是dfs一遍用线段树维护深度做的)，那么这个白点可以看做那个黑点了，只不过计算距离时要多加一个值，然后dfs一遍，对于虚树上的每条边都计算一下它对两个端点答案的贡献，具体的贡献是原树在这条链上所有的点及其子树。好像不在虚树边上的点答案不好算，于是对于每个黑点把它的初始答案设为它的所有白点siz的最大值(虚树的根的最近的黑点初始答案设为n)，枚举每条边时就只需从答案中减去不是黑点控制的即可。
复杂度\(O(logn*\sum m)\)。

#include
#include
#include
#include
#include
#include
#include
#define P puts("lala")
#define cp cerr<<"lala"<'9'){if(ch=='-')g=-1; ch=getchar();}
    while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar();
    return re*g;
}
typedef long long ll;
typedef pair pii;

const int N=300050;
const int inf=0x3f3f3f3f;
int head[N],cnt=0;
struct node
{
    int to,next,w;
}e[N<<1];
inline void add(int x,int y,int w)
{
    e[++cnt]=(node){y,head[x],w};head[x]=cnt;
    e[++cnt]=(node){x,head[y],w};head[y]=cnt;
}
int n,f[N][23],dep[N],m,dfn[N],clk=0,efn[N];
void dfs(int u,int fa,int d)
{
    f[u][0]=fa; dep[u]=d; dfn[u]=++clk;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u,d+1);
    }
    efn[u]=clk;
}
inline int lca(int x,int y)
{
    if(dep[x]=0;--i) if(d&1<=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]>1;
        build(o<<1,l,mid); build(o<<1|1,mid+1,r);
        minv[o]=min(minv[o<<1],minv[o<<1|1]);
    }
    inline void pushdown(int o)
    {
        if(add[o])
        {
            add[o<<1]+=add[o]; add[o<<1|1]+=add[o];
            minv[o<<1].fi+=add[o]; minv[o<<1|1].fi+=add[o];
            add[o]=0;
        }
    }
    void update(int o,int l,int r,int x,int y,int k)
    {
        if(x<=l&&r<=y) {add[o]+=k; minv[o].fi+=k; return ;}
        pushdown(o);
        int mid=l+r>>1;
        if(x<=mid) update(o<<1,l,mid,x,y,k);
        if(y>mid) update(o<<1|1,mid+1,r,x,y,k);
        minv[o]=min(minv[o<<1],minv[o<<1|1]);
    }
}

int vt[N],tot=0,stk[N],top=0,last[N],dfn2[N],efn2[N],clk2=0,Ans[N];
pii p[N];

inline int getfa(int x,int k)
{
    k=max(k,0);
    for(int i=19;i>=0;--i) if(k&1<efn[stk[top]]) top--;
            add(stk[top],vt[i],dep[vt[i]]-dep[stk[top]]);
            stk[++top]=vt[i];
        }

        clk2=0;
        dfs1(vt[1],0,0);
        seg::build(1,1,tot);
        dfs2(vt[1],0);

        Ans[p[vt[1]].se]=n;
        dfs3(vt[1],0);
        for(int i=1;i<=siz;++i) printf("%d ",Ans[ve[i]]);
        ln;

        for(int i=1;i<=tot;++i) black[vt[i]]=0;
    }
    return 0;
}