5分没过样例代码求调 qwq
查看原帖
5分没过样例代码求调 qwq
632955
伊地知虹夏楼主2023/4/3 21:59
//线段树合并
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct Sgt{
    int l,r,mx,id;
}tr[N*100];
#define l(i) tr[i].l
#define r(i) tr[i].r
#define mx(i) tr[i].mx
#define id(i) tr[i].id
#define lg 21
int n,m,tot;
int dep[N],F[N][lg+2];
vector<int> G[N];
int root[N];
void pushup(int cur){
    if(!l(cur) && !r(cur))//判空
        return;
    if (mx(l(cur)) >= mx(r(cur)))                 // 线段树编号原则:越靠左越小
        mx(cur) = mx(l(cur)),id(cur) = id(l(cur));//区别于传统编号原则
    else
        mx(cur) = mx(r(cur)),id(cur) = id(r(cur));
}
void insert(int &cur,int x,int v,int l,int r){
    if(!cur) cur = ++tot;//开点
    if(l == r && l == x){
        id(cur) = x,mx(cur) += v;//加上
        return;
    }
    int mid = l + r >> 1;
    if(x <= mid)
        insert(l(cur), x, v, l, mid);
    else 
        insert(r(cur), x, v, mid + 1, r); // 开左右子树
    pushup(cur);
}
int merge(int r1,int r2,int l,int r){
    if(!r1 || !r2) return r1||r2;//一个小小的简写,为零就会返回另一个
    int p = ++tot;
    if(l == r){
        mx(p) = mx(r1)+mx(r2);//合并叶子节点的值
        id(p) = l;//当前是 l 号节点啊
        return p;//要return
    }
    int mid = l+r>>1;
    l(p) = merge(l(r1), l(r2), l, mid);
    r(p) = merge(r(r1), r(r2), mid + 1, r); // 递归合并左右子树
    pushup(p);
    return p;
}
//LCA
void dfs(int cur,int fa){
    dep[cur] = dep[fa]+1;
    F[cur][0] = fa;
    for(int i = 1;i <= lg;i ++)
        F[cur][i] = F[F[cur][i-1]][i-1];
    for(auto nxt:G[cur])
        if(nxt != fa)
            dfs(nxt,cur);
    return ;
}
int Lca(int x,int y){
    if(dep[y] > dep[x]) swap(x,y);
    int dis = dep[x]-dep[y];
    for(int i = 0;i <= lg;i ++)
        if(dis & (1 << i)) 
            dis -= (1 << i),x = F[x][i];
    if(x == y) return x;
    for(int i = lg;i >= 0;i --)
        if(F[x][i] != F[y][i])
            x = F[x][i],y = F[y][i];
    return F[x][0];
}
//逆差分
void dfs2(int cur,int fa){
    for(auto nxt:G[cur])
        if(nxt != fa){
            dfs2(nxt,cur);
            root[cur] = merge(root[cur],root[nxt],1,N-5);
        }
    return ;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1;i < n;i ++){
        int x,y;
        cin >> x >> y;
        G[x].push_back(y);G[y].push_back(x);
    }
    G[1].push_back(0);
    G[0].push_back(1);
    dfs(0, 0);
    for(int i = 1;i <= m;i ++){
        int x,y,z;
        cin >> x >> y >> z;
        int A = Lca(x,y);
        insert(root[A],z,-1,1,N-5);
        insert(root[F[A][0]],z,-1,1,N-5);
        insert(root[x],z,1,1,N-5);
        insert(root[y],z,1,1,N-5);
    }
    dfs2(0,0);
    for(int i = 1;i <= n;i ++){
        if(!mx(root[i]) ) cout << "0\n";
        else cout << id(root[i]) << '\n';
    }
    return 0;
}

2023/4/3 21:59
加载中...