P4556题解

· · 个人记录

思路

利用线段树合并来辅助完成差分

做法

为了快速求出每个点的信息，可以树上差分，最后一遍 dfs 统一处理。

因为一个点可以有很多种救济粮，而要维护的信息是每个点数量最多的救济粮的具体数量及种类，所以可以每个点都开一个权值线段树，维护以上信息。

差分的时候，将 x,y 点维护的 z 型救济粮数量加一，代表 1 \rightarrow x 和 1 \rightarrow y 路径上的所有点 z 型救济数量加一。由于 lca(x,y) 多算了一次，1 \rightarrow father(lca(x,y) 路径多算了两次，所以将 将 lca(x,y) 以及 father(lca(x,y)) 两个点维护的 z 型救济粮数量减一，去除多余贡献。

最后统一 dfs 的时候，将每个点与子树的贡献合并就行了。

最后，应该动态开点。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=1e5+5;
    int n,m;
    int head[maxn];
    int maxr=0;
    struct EDGE
    {
        int to,nxt;
    }edge[maxn<<1];
    int cnt;
    inline void add(int u,int to)
    {
        edge[++cnt].to=to;
        edge[cnt].nxt=head[u];
        head[u]=cnt;
    }
    int fa[18][maxn],dep[maxn];
    void dfs(int u,int _fa)
    {
        dep[u]=dep[_fa]+1;
        fa[0][u]=_fa;
        for(int i=1;i<=17;i++)
        {
            fa[i][u]=fa[i-1][fa[i-1][u]];
        }
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==_fa)continue;
            dfs(to,u);
        }
    }
    inline int lca(int a,int b)
    {
        if(dep[a]<dep[b])swap(a,b);
        for(int i=17;i>=0;i--)
        {
            if(dep[fa[i][a]]>=dep[b])
            {
                a=fa[i][a];
            }
        }
        if(a==b)return a;
        for(int i=17;i>=0;i--)
        {
            if(fa[i][a]!=fa[i][b])
            {
                a=fa[i][a];
                b=fa[i][b];
            }
        }
        return fa[0][a];
    }
    struct Tree
    {
        int ls,rs,maxval,maxzl;
    }tree[maxn*100];
    int x[maxn],y[maxn],z[maxn];
    int nodecnt;
    int rt[maxn];//原来节点对应的线段树节点编号
    inline void push_up(int node)
    {
        if(tree[tree[node].ls].maxval>=tree[tree[node].rs].maxval)
        {
            tree[node].maxval=tree[tree[node].ls].maxval;
            tree[node].maxzl=tree[tree[node].ls].maxzl;
        }
        else
        {
            tree[node].maxval=tree[tree[node].rs].maxval;
            tree[node].maxzl=tree[tree[node].rs].maxzl;
        }
    }
    int modify(int node,int l,int r,int pos/*要修改的位置*/,int val)
    {
        if(!node)node=++nodecnt;
        if(l==r)
        {
            tree[node].maxval+=val;
            tree[node].maxzl=l;
            return node;
        }
        int mid=l+r>>1;
        if(mid>=pos)
        {
            tree[node].ls=modify(tree[node].ls,l,mid,pos,val);
        }
        else tree[node].rs=modify(tree[node].rs,mid+1,r,pos,val);
        push_up(node);
        return node;
    }
    int merge(int a,int b,int l,int r)
    {
        if(!a)return b;
        if(!b)return a;
        int _rt=++nodecnt;
        if(l==r)
        {
            tree[_rt].maxval=tree[a].maxval+tree[b].maxval;
            tree[_rt].maxzl=l;
            return _rt;
        }
        int mid=l+r>>1;
        tree[_rt].ls=merge(tree[a].ls,tree[b].ls,l,mid);
        tree[_rt].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);
        push_up(_rt);
        return _rt;
    }
    int ans[100005];
    void REdfs(int u,int _fa)
    {
        assert(u<=1e5);
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==_fa)continue;
            REdfs(to,u);
            rt[u]=merge(rt[u],rt[to],1,maxr);
        }
        if(tree[rt[u]].maxval)
            ans[u]=tree[rt[u]].maxzl;
    }
    void main()
    {
        scanf("%d%d",&n,&m);
        int ai,bi;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&ai,&bi);
            add(ai,bi);
            add(bi,ai);
        }
        dfs(1,0);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x[i],&y[i],&z[i]);
            maxr=max(maxr,z[i]);
        }
        for(int i=1;i<=m;i++)
        {
            assert(x[i]<=1e5&&y[i]<=1e5);
            rt[x[i]]=modify(rt[x[i]],1,maxr,z[i],1);
            rt[y[i]]=modify(rt[y[i]],1,maxr,z[i],1);
            int _lca=lca(x[i],y[i]);
            rt[_lca]=modify(rt[_lca],1,maxr,z[i],-1);
            if(fa[0][_lca])
                rt[fa[0][_lca]]=modify(rt[fa[0][_lca]],1,maxr,z[i],-1);
        }
        REdfs(1,0);
        for(int i=1;i<=n;i++)
        {
            printf("%d\n",ans[i]);
        }
    }
}
int main()
{
    Main::main();
    return 0;
}