题解 P3899 【[湖南集训]谈笑风生】

· · 题解

线段树合并只打12分可太难了TvT

看来好多红名巨佬都跟我一样是从12分改过来的，其实是因为合并u点的线段树的时候把儿子的线段树信息给改了，那本蒟蒻就主要说说动态开点线段树的深度理解。

sol

首先看如果b和a没有祖先后代关系，a和b肯定不能同时是c的祖先，不成立；

如果b是a的祖先，方案数就是\min(K,depth[a]-1)*(size[a]-1);

如果b是a的后代，方案数就是深度在depth[a]+1到depth[a]+K之间每个b的(size[b]-1)之和，那么可以用线段树合并来做，线段树下标表示深度，记区间的(size-1)之和，求线段树在(depth[a]+1,depth[a]+K)的区间和。

但是merge函数如果这么写的话（没新开节点，直接更新x的信息）就会获得12分的好成绩TvT：

int merge(int x,int y,int tl,int tr) {
    if(x==0||y==0) return x|y;//有空节点。
    if(tl==tr) {
        tree[x].num=tree[x].num+tree[y].num;
        return x;
    }![](lf[wpepwkf)
    int mid=(tl+tr)/2;
    tree[x].ls=merge(tree[x].ls,tree[y].ls,tl,mid);
    tree[x].rs=merge(tree[x].rs,tree[y].rs,mid+1,tr);
    up(x);//上传维护值。
    return x;
}

只有新开了线段树节点才能A：

int merge(int x,int y,int tl,int tr) {
    if(x==0||y==0) return x|y;//有空节点。

    if(tl==tr) {
        int now=++tot;
        tree[now].num=tree[x].num+tree[y].num;
        return now;
    }
    int mid=(tl+tr)/2,now=++tot;//为了不改变儿子线段树的值，必须新建节点。
    tree[now].ls=merge(tree[x].ls,tree[y].ls,tl,mid);
    tree[now].rs=merge(tree[x].rs,tree[y].rs,mid+1,tr);
    up(now);
    return now;
}

所以本篇题解详细讲一下产生这种情况的原因。

线段树合并

要合并x和y两颗线段树，如果直接合并的话，x上的1号点右儿子直接赋成y上的2号点了，这样的话，x再和另一颗线段树合并，有可能改变2号点以及2号点子树的信息，y的信息就被乱改了。ovo

如果每次要合并的时候都给x新开一个节点，y的信息就不会被乱改了，每个点合并之后儿子的信息还是准确的。*v*

但是x线段树递归到某个空子树的时候，还是要把y上对应的子树拿过来，这可以相当于是打标记，暂时用了y的子树。正经合并的时候肯定是不能改变y的信息了。

这样就能A掉这道题了……

#include<bits/stdc++.h>
using namespace std;
const int mv=3e5,ml=19;

int n,q;
struct node{
    int ls,rs;
    long long num;//每个点的siz-1之和。
}tree[2*mv*ml+3];int tot=0;
inline void up(int x) {
    tree[x].num=tree[tree[x].ls].num+tree[tree[x].rs].num;
}
void add(int x,int tl,int tr,int w,int ad) {
    if(tl==tr) {
        tree[x].num+=ad;
        return;
    }

    int mid=(tl+tr)/2;
    if(w<=mid) {
        if(!tree[x].ls) tree[x].ls=++tot;
        add(tree[x].ls,tl,mid,w,ad);
    }
    if(w>mid) {
        if(!tree[x].rs) tree[x].rs=++tot;
        add(tree[x].rs,mid+1,tr,w,ad);
    }
    up(x);
}
long long askS(int x,int tl,int tr,int l,int r) {
    if(!x) return 0;
    if(tl==l&&r==tr) return tree[x].num;

    int mid=(tl+tr)/2;long long ans=0;
    //没建出来的地方值肯定为0，不用递归。
    if(l<=mid&&tree[x].ls) 
        ans+=askS(tree[x].ls,tl,mid,l,min(mid,r));
    if(r>mid&&tree[x].rs) 
        ans+=askS(tree[x].rs,mid+1,tr,max(l,mid+1),r);
    return ans;
}
int merge(int x,int y,int tl,int tr) {
    if(x==0||y==0) return x|y;//有空的则返回非空的。

    if(tl==tr) {
        int now=++tot;
        tree[now].num=tree[x].num+tree[y].num;
        return now;
    }
    int mid=(tl+tr)/2,now=++tot;//为了不改变儿子线段树的值，必须新建节点。
    tree[now].ls=merge(tree[x].ls,tree[y].ls,tl,mid);
    tree[now].rs=merge(tree[x].rs,tree[y].rs,mid+1,tr);
    up(now);
    return now;
}

vector<int>po[mv+3];
int fa[mv+3],h[mv+3],siz[mv+3],rtw[mv+3];
//父亲、深度、子树大小、该点对应线段树树根的编号。
void dfs(int u) {
    siz[u]=1;
    for(int j=0;j<(int)po[u].size();j++) {
        int v=po[u][j];
        if(fa[u]==v) continue;

        fa[v]=u;
        h[v]=h[u]+1;
        dfs(v);
        siz[u]+=siz[v];
    }

    rtw[u]=++tot;
    add(rtw[u],1,n,h[u],siz[u]-1);//在线段树深度为h处加答案。
    for(int j=0;j<(int)po[u].size();j++) {
        int v=po[u][j];
        if(fa[u]==v) continue;

        rtw[u]=merge(rtw[u],rtw[v],1,n);//合并。
    }
}

int main() {
    cin>>n>>q;
    int u,v;
    for(int e=1;e<n;e++) {
        scanf("%d%d",&u,&v);
        po[u].push_back(v);
        po[v].push_back(u);
    }
    h[1]=1;//深度从1开始记。
    dfs(1);

    int K;
    for(int z=1;z<=q;z++) {
        scanf("%d%d",&u,&K);
        long long ans=1ll*min(h[u]-1,K)*(siz[u]-1);//上方谈笑风生。
        ans+=askS(rtw[u],1,n,h[u]+1,h[u]+K);//下方谈笑风生。
        printf("%lld\n",ans);
    }
    return 0;
}