P4556 [Vani有约会]雨天的尾巴

港控/mmm° 2023-06-11 06:24 17阅读 0赞

本来刚上课，想要学一下线段树合并，一看模板题？？？？树剖。然后打了一半板子，思路断了，，，

又回去看了一会，打了树剖，一看表，，，，下课了，，

思路如下：

//树剖
    //将修改离线分割
    //线段树
    //从1 到n更新，到每个点我们知道要删除什么添加什么，然后这个点对应的答案也就出来了。
    #include<bits/stdc++.h>
    using namespace std;
    const int M=1e5+5;
    struct Edge
    {
        int to,nex;
    } e[M<<1];
    struct Node
    {
        int l,r,cnt,type;
    } t[M<<2];
    int n,m,head[M<<1],cnt;
    int fa[M],siz[M],dep[M],son[M],rk[M],id[M],top[M],tot,res[M];
    vector<int> a[M];
    
    void dfs1(int x,int f)
    {
        fa[x]=f;
        dep[x]=dep[f]+1;
        siz[x]=1;
        for(int to,i=head[x]; ~i; i=e[i].nex)
        {
            to=e[i].to;
            if(to==f)
                continue;
            dfs1(to,x);
            siz[x]+=siz[to];
            if(siz[son[x]]<siz[to])
                son[x]=to;
        }
    }
    void dfs2(int x,int tp)
    {
        top[x]=tp;
        id[x]=++tot;
        rk[tot]=x;
        if(son[x])
            dfs2(son[x],tp);
        for(int to,i=head[x]; ~i; i=e[i].nex)
        {
            to=e[i].to;
            if(to!=fa[x]&&to!=son[x])
                dfs2(to,to);
        }
    }
    void pre_work(int x,int y,int z) //预处理
    {
        int fx=top[x],fy=top[y];
        while(fx!=fy)
        {
            if(dep[fx]<dep[fy])
                swap(x,y),swap(fx,fy);
            a[id[fx]].push_back(z);
            a[id[x]+1].push_back(-z);
            x=fx;
            fx=top[x];
        }
        if(dep[x]<dep[y])
            swap(x,y);
        a[id[x]].push_back(z);
        a[id[y]+1].push_back(z);
    }
    void build(int k,int l,int r)
    {
        t[k].l=l;
        t[k].r=r;
        if(l==r)
        {
            t[k].type=l;
            return ;
        }
        int mid=(l+r)>>1;
        build(k*2,l,mid);
        build(k*2+1,mid+1,r);
    }
    void update(int k,int in,int v)
    {
        if(l==r)
        {
            t[k].cnt+=v;//这个桶的个数加1
            return ;
        }
        int mid=(l+r)>>1;
        if(in<=mid)
        {
            update(k*2,in,v);
        }
    
        else
        {
            update(k*2+1,in,v);
        }
        if(t[k*2].cnt<=t[k*2+1].cnt)
            t[k].cnt=t[k*2].cnt;
        t[k].type=t[k*2].type;
        else
        {
            t[k].cnt=t[k*2+1].cnt;
            t[k].type=t[k*2+1].type;
        }
    
    }
    int main()
    {
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&m);
        for(int x,y,i=1; i<=n; i++)
        {
            scanf("%d%d",&x,&y);
            e[cnt].to=y;
            e[cnt].nex=head[x];
            head[x]=cnt++;
            e[cnt].to=x;
            e[cnt].nex=head[y];
            head[y]=cnt++;
        }
    
        dfs1(1,0);
        dfs2(1,1);
    
        for(int x,y,z,i=1; i<=m; i++)
            scanf("%d%d%d",&x,&y,&z),pre_work(x,y,z);
        build(1,M);
    
        for(int i=1; i<=n; i++)
        {
            for(int j=0; j<a[i].size(); j++)
                if(a[i][j]>0)
                    update(1,a[i][j],1);
                else
                    update(1,-a[i][j],-1);
            res[rk[i]]=t[1].type;
        }
        return 0;
    }