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

思路
优化
过程中的问题/疑问
错误
代码

思路

每个节点维护一课线段树(当然是动态开点)
线段树的作用是统计这个节点有多少种粮食型号，以及最多的粮食型号
然后树上差分，u和v点 +1，lca(u,v)和f[lca(u,v)] -1(不显然就画图喽)
并不用转化为dfs序
只需要dfs一边，自底向上合并就好

优化

删除节点不必建树
因为在递归到他的时候一定是存在的
（要不他还能减成负数吗、、）
但在一开始建树的时候就不一定存在了
所以记录下来就好

过程中的问题/疑问

这合并真的靠谱吗
如果两个线段树都是满二叉那不凉凉了

先引用博客大佬一段:
这样子做时间复杂度取决于重合节点个数
因为满二叉树的结点数是O(n)
对每个结点进行处理是O(logn)
最坏复杂度是O(nlogn),

看着很凉，但是一点也不凉(说出了什么b话)
假设一个为满二叉
最坏复杂度的情况一定是重合部分最多的时候
也就是每条链都是分开的(一条链子合并复杂度最坏为logn)
一次修改4个点，一共修改4n个点 (n,m同阶的话)
那复杂度就是4nlogn也就是nlogn了
平均每棵树4点，实际上也不会每次修改logn
Emma，应该是这样

错误

n并不是救济粮型号的范围
所以建树应该是1到10w而不是n
zz了，2333

代码

//￠￠￡
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=1e5+7;
const int N=1e5;
inline int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m,ans[maxn],cnt,rt[maxn];
vector<int> delet[maxn];
int ch[maxn*50][2],ma[maxn*50],id[maxn*50];

//关于图 
struct edge {int v,nxt;}e[maxn<<1];
int head[maxn<<1],tot;
void add_edge(int u,int v) {e[++tot].v=v;e[tot].nxt=head[u];head[u]=tot;}

namespace LCA {
    int dep[maxn],st[maxn][21];
    void dfs(int u,int f) {
        for(int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if(v==f) continue;
            dep[v]=dep[u]+1;
            st[v][0]=u;
            dfs(v,u);
        }
    }
    int lca(int x,int y) {
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=20;i>=0;--i)
            if(dep[st[x][i]]>=dep[y])
                x=st[x][i];
        if(x==y) return x;
        for(int i=20;i>=0;--i)
            if(st[x][i]!=st[y][i])
                x=st[x][i],y=st[y][i];
        return st[x][0];
    }
    void init() {
        dep[1]=1;
        dfs(1,0);
        FOR(j,1,20) FOR(i,1,n)
        st[i][j]=st[st[i][j-1]][j-1];
    }
}

void pushup(int now) {
    ma[now]=max(ma[ch[now][0]],ma[ch[now][1]]);
    id[now]=ma[ch[now][0]]>=ma[ch[now][1]] ? id[ch[now][0]] : id[ch[now][1]];
    //加了=才会有题目中的优先级 
}
void build(int &now,int l,int r,int k,int up) {
    if(!now) now=++cnt;
    if(l==r) { 
        ma[now]+=up;
//      id[now]=!ma[now] ? 0 : l;
        return;
    }
    int mid=(l+r)>>1;
    if(k<=mid) build(ch[now][0],l,mid,k,up);
    else build(ch[now][1],mid+1,r,k,up);
    pushup(now);
}
int merge(int l,int r,int x,int y) {
    if(!x||!y) return x+y;
    if(l==r) {ma[x]+=ma[y];id[x]=l;return x;}
    int mid=(l+r)>>1;
    ch[x][0]=merge(l,mid,ch[x][0],ch[y][0]);
    ch[x][1]=merge(mid+1,r,ch[x][1],ch[y][1]);
    pushup(x);
    return x;   
}
void dfs(int u,int f) {
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(v==f) continue; 
        dfs(v,u);
        rt[u]=merge(1,N,rt[u],rt[v]);
    }
    for(vector<int>::iterator it=delet[u].begin();it!=delet[u].end();++it)
        build(rt[u],1,N,*it,-1);
    ans[u]=id[rt[u]];
}
int main() {
    n=read(),m=read();
    FOR(i,2,n) {
        int x=read(),y=read();
        add_edge(x,y),add_edge(y,x);
    }
    LCA::init(); 
    FOR(i,1,m) {
        int x=read(),y=read(),z=read();
        int tmp=LCA::lca(x,y);
        build(rt[x],1,N,z,1);
        build(rt[y],1,N,z,1);
        delet[tmp].push_back(z);
        delet[LCA::st[tmp][0]].push_back(z);
    }
    dfs(1,0);
    FOR(i,1,n) cout<<ans[i]<<"\n";
    return 0;
}