线段树合并学习笔记（P4556）

直入主题：

学习线段树合并.....

从名字就能看出，这个东西要合并线段树.....

线段树怎么能合并呢......

暴力合就行了啊......

一次从上往下的遍历，把所有的节点信息暴力合并，然后就没有然后了.....

有两种合并方法：

一、动态开点

就是主席树那样的模式（可持久化了），新开一个点记录新的节点信息，但是空间~巨~大~无~比~

然后可能需要删除节点（以前的，既然合并了，就不需要旧的了233....）

二、静态开点（口胡的）

像启发式合并那样，直接把a的信息全加到b上（虽然没有任何启发式），但是可能破坏a树的形态

于是放一发模板题（本蒻第一次封装结构体233）

（感觉就是主席树233）

首先，思路树上差分，但是具体怎么玩呢？

一个暴力的思路：

对于每一个给定的补给点，建一棵权值线段树，其他的点也有线段树但是是空树，然后在差分的时候直接把所有的点给合并起来，最后统计答案。

线段树维护的是最值。

注意的是：差分：a+1，b+1，lca-1，lca的父节点+1，这个父节点是为了消除向上的影响，只维护路径上的值。

注释在代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+;

int n,m;

struct edge

{

    int to,next;

}e[maxn];

int head[maxn],cnt;

inline void addedge(int from,int to)

{

    e[++cnt].next=head[from];

    e[cnt].to=to;

    head[from]=cnt;

}

int dep[maxn];

int f[maxn][];

int dfs(int u,int fa)

{

    dep[u]=dep[fa]+;

    for(int i=head[u];i;i=e[i].next)

    {

        int v=e[i].to;

        if(v==fa)

        continue;

        dfs(v,u);

        f[v][]=u;

    }

}

int rt[maxn];

struct segtree//第一次封装结构体

{

    int lc[maxn*],rc[maxn*],ma[maxn*],id[maxn*],root=;

    void pushup(int p)//更新最值

    {

        if(ma[lc[p]]>=ma[rc[p]])

        {

            ma[p]=ma[lc[p]];id[p]=id[lc[p]];//值得注意的是：这个id是记录答案的，所以要一起更新

        }

        else

        {

            ma[p]=ma[rc[p]];id[p]=id[rc[p]];

        }

    }

    int merge(int a,int b,int l,int r)

    {

        if(!a||!b)//如果一个是空的，那就返回有值的那个节点

        return a+b;

        if(l==r)

        {

            ma[a]=ma[a]+ma[b],id[a]=l;//如果是叶节点就更新

            return a;

        }

        int mid=l+r>>;

        lc[a]=merge(lc[a],lc[b],l,mid);//向下合并

        rc[a]=merge(rc[a],rc[b],mid+,r);//向下合并

        pushup(a);//记得更新

        return a;

    }

    void insert(int &x,int l,int r,int p,int k)

    {

        if(x==)

        x=++root;//十分类似主席树的插入

        if(l==r)

        {

            id[x]=l;

            ma[x]+=k;

            return;

        }

        int mid=l+r>>;

        if(p<=mid)insert(lc[x],l,mid,p,k);

        else    insert(rc[x],mid+,r,p,k);

        pushup(x);

    }

}T;

int lca(int a,int b)//平淡无奇的lca

{

    if(dep[a]<dep[b])

    swap(a,b);

    for(int i=;i>=;i--)

    {

        if(dep[b]<=dep[a]-(<<i))

        a=f[a][i];

    }

    if(a==b)

    return a;

    for(int i=;i>=;i--)

    {

        if(f[a][i]!=f[b][i])

        {

            a=f[a][i];

            b=f[b][i];

        }

    }

    return f[a][];

}

int ans[maxn];

void dfsans(int u,int fa)

{

    for(int i=head[u];i;i=e[i].next)

    {

        int v=e[i].to;

        if(v==fa)

        continue;

        dfsans(v,u);

        rt[u]=T.merge(rt[u],rt[v],,);//合并

    }

    ans[u]=T.id[rt[u]];//更新答案

    if(T.ma[rt[u]]==)

    ans[u]=;//记得特判0的情况

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<n;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        addedge(x,y);

        addedge(y,x);

    }

    dfs(,);

    for(int i=;i<=;i++)

    {

        for(int j=;j<=n;j++)

        {

            f[j][i]=f[f[j][i-]][i-];

        }

    }

    for(int i=;i<=m;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        int u=lca(x,y);

        T.insert(rt[u],,,z,-);

        T.insert(rt[x],,,z,);

        T.insert(rt[y],,,z,);

        T.insert(rt[f[u][]],,,z,-);

    }

    dfsans(,);

    for(int i=;i<=n;i++)

    printf("%d\n",ans[i]);

    return ;

}

（完）

巴特西

线段树合并学习笔记（P4556）

最新文章

热门文章