题目描述

深绘里一直很讨厌雨天。

灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。

虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。

无奈的深绘里和村民们只好等待救济粮来维生。

不过救济粮的发放方式很特别。

有 n 个点，形成一个树状结构。

有 m 次发放操作，每次选择两个点 x,y，对 x 到 y 的路径上（包括 x,y）的每个点发放一袋 z 类型的物品。

求完成所有发放操作后，每个点存放最多的是哪种类型的物品。

输入格式

第一行两个正整数n,m，含义如题目所示。

接下来n-1行，每行两个数(a,b)，表示(a,b)间有一条边。

再接下来m行，每行三个数(x,y,z)，含义如题目所示。

输出格式

共n行，第i行一个整数，表示第i座房屋里存放的最多的是哪种救济粮，如果有多种救济粮存放次数一样，输出编号最小的。

如果某座房屋里没有救济粮，则对应一行输出0。

线段树合并——$O(nlogn)$

离散化+树上差分+线段树合并
由于z太大首先离散化，对于树上的每一个点考虑维护一个cnt[]数组记录种累数量，对于树上节点x->y的路径上的节点种类z加1，考虑树上差分分解成pxy=lca(x,y),ppxy=fa[pxy][0]，对于x节点和y节点z种类的数量加一，即cnt[z]++，而对于pxy节点和ppxy节点z种类的数量减一，即cnt[z]--。由于差分需要合并，每个节点需要把所有子树的cnt[]数组合并才会得到原来的cnt[]，由于数组合并总花费$O(n^2)$代价，考虑使用权值线段树维护数组cnt[]，对于线段树合并总复杂度经证明只需花费$O(nlogn)$的代价。权值线段树维护cnt[]数组。
对于答案需要找到种类最多的编号考虑query或者在维护区间最值的同时再维护一个id即可。
对于下面两种代码cin均TLE1个点

代码1

只维护区间最值val最后query答案

//O(nlogn)常数很大——4979 ms
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=100010;
int h[N],e[2*N],ne[2*N],idx;
int n,m,M;
int x[N],y[N],z[N];
int ans[N];
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int fa[N][18],dep[N];
void dfs1(int u)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(dep[j]) continue;
        dep[j]=dep[u]+1;
        fa[j][0]=u;
        for(int k=1;k<=17;k++)  
            fa[j][k]=fa[fa[j][k-1]][k-1];
        dfs1(j);
    }
}
int lca(int a,int b)
{
    if(dep[a]<dep[b]) swap(a,b);
    for(int k=17;k>=0;k--)
        if(dep[fa[a][k]]>=dep[b])
            a=fa[a][k];
    if(a==b) return a;
    for(int k=17;k>=0;k--)
        if(fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    return fa[a][0];
}
vector<int> mpz;
int find(int x)
{
    return lower_bound(mpz.begin(),mpz.end(),x)-mpz.begin();
}
struct node
{
    int l,r;
    int val;
}tree[N*60];
int root[N],cnt;
void modify(int &u,int l,int r,int c,int d)
{
    if(!u) u=++cnt;
    if(l==r) 
    {
        tree[u].val+=d;
        return;
    }
    int mid=l+r>>1;
    if(c<=mid) modify(tree[u].l,l,mid,c,d);
    else modify(tree[u].r,mid+1,r,c,d);
    tree[u].val=max(tree[tree[u].l].val,tree[tree[u].r].val);
}
int merge(int x,int y,int l,int r)
{
    if(!x||!y) return x+y;
    int mid=l+r>>1;
    if(l==r)
    {
        tree[x].val+=tree[y].val;
        return x;
    }
    tree[x].l=merge(tree[x].l,tree[y].l,l,mid);
    tree[x].r=merge(tree[x].r,tree[y].r,mid+1,r);
    tree[x].val=max(tree[tree[x].l].val,tree[tree[x].r].val);
    return x;
}
int query(int u,int l,int r)
{
    if(l==r) return l;
    int mid=l+r>>1;
    if(tree[tree[u].l].val>=tree[tree[u].r].val) return query(tree[u].l,l,mid);
    else return query(tree[u].r,mid+1,r);
} 
void dfs2(int u)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(fa[u][0]==j) continue;
        dfs2(j);
        root[u]=merge(root[u],root[j],0,M);
    }
    ans[u]=mpz[query(root[u],0,M)];//一定要合并完统计答案要不然在此合并时维护信息会改变
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    // 预处理倍增数组
    dep[1]=1;
    dfs1(1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
        mpz.push_back(z[i]);
    }
    mpz.push_back(0);//哨兵
    sort(mpz.begin(),mpz.end());
    mpz.erase(unique(mpz.begin(),mpz.end()),mpz.end());
    M=mpz.size()-1;
    for(int i=1;i<=n;i++) modify(root[i],0,M,0,0);
    for(int i=1;i<=m;i++)
    {
        int a=x[i],b=y[i],c=find(z[i]);
        int pab=lca(a,b),ppab=fa[pab][0];

        modify(root[a],0,M,c,1),modify(root[b],0,M,c,1);
        if(pab) modify(root[pab],0,M,c,-1);
        if(ppab) modify(root[ppab],0,M,c,-1);

    }
    dfs2(1);
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

代码2

维护区间最值val的同时维护id

//O(nlogn)常数大——4404 ms
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=100010;
int h[N],e[2*N],ne[2*N],idx;
int n,m,M;
int ans[N];
int x[N],y[N],z[N];
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int fa[N][18],dep[N];
void dfs1(int u)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(dep[j]) continue;
        dep[j]=dep[u]+1;
        fa[j][0]=u;
        for(int k=1;k<=17;k++)  
            fa[j][k]=fa[fa[j][k-1]][k-1];
        dfs1(j);
    }
}
int lca(int a,int b)
{
    if(dep[a]<dep[b]) swap(a,b);
    for(int k=17;k>=0;k--)
        if(dep[fa[a][k]]>=dep[b])
            a=fa[a][k];
    if(a==b) return a;
    for(int k=17;k>=0;k--)
        if(fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    return fa[a][0];
}
vector<int> mpz;
int find(int x)
{
    return lower_bound(mpz.begin(),mpz.end(),x)-mpz.begin();
}
struct node
{
    int l,r;
    int val,id;
}tree[N*60];
int root[N],cnt;
void pushup(int u)
{
    if(tree[tree[u].l].val>=tree[tree[u].r].val)
    {
        tree[u].id=tree[tree[u].l].id;
        tree[u].val=tree[tree[u].l].val;
    }
    else 
    {
        tree[u].id=tree[tree[u].r].id;
        tree[u].val=tree[tree[u].r].val;
    }
}
void modify(int &u,int l,int r,int c,int d)
{
    if(!u) u=++cnt;
    if(l==r) 
    {
        tree[u].id=l;
        tree[u].val+=d;
        return;
    }
    int mid=l+r>>1;
    if(c<=mid) modify(tree[u].l,l,mid,c,d);
    else modify(tree[u].r,mid+1,r,c,d);
    pushup(u);
}
int merge(int x,int y,int l,int r)
{
    if(!x||!y) return x+y;
    if(l==r)//叶子
    {
        tree[x].val+=tree[y].val;
        return x;
    }

    int mid=l+r>>1;
    tree[x].l=merge(tree[x].l,tree[y].l,l,mid);
    tree[x].r=merge(tree[x].r,tree[y].r,mid+1,r);
    pushup(x);
    return x;
}
void dfs2(int u)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(fa[u][0]==j) continue;
        dfs2(j);
        root[u]=merge(root[u],root[j],0,M);
    }
    ans[u]=mpz[tree[root[u]].id];
}
int main()
{

    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
        mpz.push_back(z[i]);
    }
    // 预处理倍增数组
    dep[1]=1;
    dfs1(1);
    mpz.push_back(0);//哨兵
    sort(mpz.begin(),mpz.end());
    mpz.erase(unique(mpz.begin(),mpz.end()),mpz.end());
    M=mpz.size()-1;
    for(int i=1;i<=m;i++)
    {
        int a=x[i],b=y[i],c=find(z[i]);
        int pab=lca(a,b),ppab=fa[pab][0];

        modify(root[a],0,M,c,1),modify(root[b],0,M,c,1);
        if(pab) modify(root[pab],0,M,c,-1);
        if(ppab) modify(root[ppab],0,M,c,-1);
    }
    dfs2(1);
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

树链剖分——$O(nlog^2n)$

对于树上链操作，当然少不了树链剖分大法（别看复杂度比线段树合并高，但是跑的比线段树合并快）
树链剖分可以将树上的链操作转化为一些连续的区间操作。
每个点仍然维护一个权值线段树，然后考虑差分进行区间端点加减，这样做似乎还要进行线段树合并
树剖后，我们会得到dfn[]，可以把dfn[]看成一条时间轴，那么一些连续的区间操作可以看成在时间轴的某个时刻进行加减操作，尝试用一棵权值线段树维护，当在询问dfn[u]时刻时只要保证在该时刻以及之前的时刻的操作都已经操作完成自然该权值线段树即是一棵前缀线段树。

1.开始时，将路径的修改拆分成一个个编号连续的区间$[a_i,b_i]$，对于每个区间有用差分思想拆为$a_i$处c的个数+1，$b_i$处c的个数-1,用邻接表的方式存下每个编号（时间）所对应的的各个修改。

2.然后，从1时刻开始遍历所有修改，在一颗权值线段树上执行，每个时刻的修改遍历完之后，将该时刻对应的节点的答案记录下来。该时刻以及之前的时刻的操作都已经操作完成自然该权值线段树即是一棵前缀线段树。

雪月千里共茗茶题解

//O(nlog^2n)——3569 ms
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int> pii;
const int N=100010;
int h[N],e[2*N],ne[2*N],idx;
int n,m,M;
int x[N],y[N],z[N];
int ans[N];
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int fa[N],dep[N],sz[N],son[N];
vector<int> mpz;
void dfs1(int u,int p)
{
    sz[u]=1;
    fa[u]=p,dep[u]=dep[p]+1;
    int mx=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==p) continue;
        dfs1(j,u);
        sz[u]+=sz[j];
        if(mx<sz[j]) 
        {
            mx=sz[j];
            son[u]=j;
        }
    }
}
int timestamp,dfn[N],top[N],id[N];
void dfs2(int u,int t)
{
    dfn[u]=++timestamp;
    id[timestamp]=u;
    top[u]=t;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i]; 
        if(j==fa[u]||son[u]==j) continue;
        dfs2(j,j);
    }
}
int find(int x)
{
    return lower_bound(mpz.begin(),mpz.end(),x)-mpz.begin();
}
struct node
{
    int l,r;
    int val,id;
}tree[N*4];
void pushup(int u)
{
    if(tree[u<<1].val>=tree[u<<1|1].val) 
    {
        tree[u].val=tree[u<<1].val;
        tree[u].id=tree[u<<1].id;
    }
    else
    {
        tree[u].val=tree[u<<1|1].val;
        tree[u].id=tree[u<<1|1].id;
    }
}
void build(int u,int l,int r)
{
    tree[u]={l,r,0,0};
    if(l==r)
    {
        tree[u].id=l;
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int c,int d)
{
    if(tree[u].l==tree[u].r)
    {
        tree[u].val+=d;
        return;
    }
    int mid=tree[u].l+tree[u].r>>1;
    if(c<=mid) modify(u<<1,c,d);
    else modify(u<<1|1,c,d);
    pushup(u);
}
vector<pii> adj[N];
void cmodify(int u,int v,int c)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        adj[dfn[top[u]]].push_back({c,1}),adj[dfn[u]+1].push_back({c,-1});
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    adj[dfn[u]].push_back({c,1}),adj[dfn[v]+1].push_back({c,-1});
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
        mpz.push_back(z[i]);
    }
    mpz.push_back(0);//哨兵
    sort(mpz.begin(),mpz.end());
    mpz.erase(unique(mpz.begin(),mpz.end()),mpz.end());
    M=mpz.size()-1;
    dfs1(1,1);
    dfs2(1,1);
    for(int i=1;i<=m;i++) cmodify(x[i],y[i],find(z[i]));
    build(1,0,M);
    for(int i=1;i<=n;i++)
    {
        for(auto t:adj[i])
            modify(1,t.first,t.second);
        ans[id[i]]=mpz[tree[1].id];
    }
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

线段树合并和树剖都是最近刚学的，如有错误或者不理解的地方请在评论区评论，互相学习共同进步谢谢。
debug调了巨长时间快崩溃了
要加油哦~