セグメントツリーチェーン分割(境界)

セグメントツリーチェーン分割(境界)

// Created by CAD on 2020/2/16.
#include 

#define lson (p<<1)
#define rson (p<<1|1)
#define ll long long
using namespace std;

//===================== =======================
const int maxn=1e5+5;
int d[maxn<<2],laz[maxn<<2],wt[maxn];
int n;
void build(int s,int t,int p){
    if(s==t){
        d[p]=wt[s];
        return ;
    }
    int mid=(s+t)>>1;
    build(s,mid,lson),build(mid+1,t,rson);
    d[p]=d[lson]+d[rson];
}
void push(int s,int t,int p){
    int mid=(s+t)>>1;
    d[lson]+=laz[p]*(mid-s+1),d[rson]+=laz[p]*(t-mid);
    laz[lson]+=laz[p],laz[rson]+=laz[p];
    laz[p]=0;
}
//----------- （l~r c）--------------
void update(int l,int r,int c,int s,int t,int p){
    if(l<=s&&t<=r){
        d[p]+=(t-s+1)*c,laz[p]+=c;
        return ;
    }
    if(laz[p]) push(s,t,p);
    int mid=(s+t)>>1;
    if(l<=mid) update(l,r,c,s,mid,lson);
    if(r>mid) update(l,r,c,mid+1,t,rson);
    d[p]=d[lson]+d[rson];
}
//----------- （l~r ）--------------
int getsum(int l,int r,int s,int t,int p){
    if(l<=s&&t<=r) return d[p];
    if(laz[p]) push(s,t,p);
    int mid=(s+t)>>1;
    ll sum=0;
    if(l<=mid) sum+=getsum(l,r,s,mid,lson);
    if(r>mid) sum+=getsum(l,r,mid+1,t,rson);
    return sum;
}
//===================== =========================
int cnt=0,head[maxn<<1];
struct edge{
    int to,w,next;
}e[maxn<<1];
void add(int u,int v,int w){
    e[++cnt]=edge{v,w,head[u]};
    head[u]=cnt;
}
//====================== =========================
int dep[maxn],id[maxn],siz[maxn],son[maxn],f[maxn],top[maxn],w[maxn];
int tot;
void dfs1(int x,int fa,int deep){
    dep[x]=deep,f[x]=fa,siz[x]=1;
    int maxson=-1;
    for(int i=head[x];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        w[v]=e[i].w;
        dfs1(v,x,deep+1);
        siz[x]+=siz[v];
        if(siz[v]>maxson) maxson=siz[v],son[x]=v;
    }
}
void dfs2(int x,int from){
    id[x]=++tot,wt[tot]=w[x];
    top[x]=from;
    if(son[x]) dfs2(son[x],from);
    for(int i=head[x];i;i=e[i].next){
        int v=e[i].to;
        if(v==son[x]||v==f[x]) continue;
        dfs2(v,v);
    }
}
//---------------- （l~r ）------------------
int qrange(int l,int r){
    int ans=0;
    while(top[l]!=top[r]){
        if(dep[top[l]]id[r]) swap(l,r);
    if(l!=r)    ans+=getsum(id[son[l]],id[r],1,n,1);
    return ans;
}
//---------------- （l~r k）------------------
void updrange(int l,int r,int k){
    while(top[l]!=top[r]){
        if(dep[top[l]]id[r]) swap(l,r);
    if(l!=r)    update(id[l],id[r],k,1,n,1);
}
//---------------- （ x k）------------------
void updson(int x,int k){
    if(siz[x]>1)
        update(id[son[x]],id[x]+siz[x]-1,k,1,n,1);
}
//---------------- （ x ）------------------
int qson(int x){
    if(siz[x]>1)
        return getsum(id[son[x]],id[x]+siz[x]-1,1,n,1);
    else return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n-1;++i){
        int u,v,wei;scanf("%d%d%d", &u, &v, &wei);
        add(u, v, wei),add(v, u, wei);
    }
    dfs1(1,0,1),dfs2(1,1),build(1,n,1);


    return 0;
}