hdu6133

201708 （ACM）数据结构----树链剖分 （ACM）数据结构----线段树

• 题解
  
  • 考虑一个点被几个点贡献，这几个点的权值从小到大排序分别是 $v1,v2,v3,v4$
  • 如果从小到达加入点，那么贡献是 $v1,v1+v2,v1+v2+v3,v1+v2+v3+v4$
  • 总贡献是 $4*v1+3*v2+2*v3+v4$
  • 如果从大到小加入点，可以发现这些东西是可以树剖之后用线段树维护的
• 总结
  
  • 懒惰标记
    
    • 当要访问当前节点的子节点的时候，需要将当前节点的标记传下去。所以访问当前节点的时候，这个节点的标记是有存东西的，不能直接覆盖。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(a) (int)a.size()
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define mp make_pair
#define dd(a) cout<<#a<<" = "<<a<<" "
#define de(a) cout<<#a<<" = "<<a<<endl
#define pb push_back
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef long long ll;
typedef pair<int, int> pii;
//----
const int N=100005;
vector<int> G[N];
int n;
int v[N];
pii a[N];
int tim;
int siz[N],top[N],son[N],dep[N],fa[N],tid[N];
void init() {
    memset(son,-1,sizeof(son));
    tim=0;
}
void dfs1(int u,int pre,int d) {
    dep[u]=d;
    fa[u]=pre;
    siz[u]=1;
    rep(i,0,sz(G[u])) {
        int v=G[u][i];
        if(v!=pre) {
            dfs1(v,u,d+1);
            siz[u]+=siz[v];
            if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
        }
    }
}
void dfs2(int u,int tp) {
    top[u]=tp;
    tid[u]=++tim;
    if(son[u]==-1) return ;
    dfs2(son[u],tp);
    rep(i,0,sz(G[u])) {
        int v=G[u][i];
        if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
    }
}
int cc[N<<2];
ll s[N<<2],ss[N<<2];
void build(int l,int r,int rt) {
    cc[rt]=s[rt]=ss[rt]=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(lson);build(rson);
}
void DOWN(int rt) {
    if(cc[rt]==0) return ;
    int L=(rt<<1),R=(rt<<1|1);
    s[L]+=s[rt];
    s[R]+=s[rt];
    ss[L]+=ss[rt]+s[rt]*cc[L];
    ss[R]+=ss[rt]+s[rt]*cc[R];
    cc[L]+=cc[rt];
    cc[R]+=cc[rt];
    cc[rt]=s[rt]=ss[rt]=0;
}
void upd(int L,int R,ll c,int l,int r,int rt) {
    if(R<l||r<L) return ;
    if(L<=l&&r<=R) {
        ++cc[rt];
        s[rt]+=c;
        ss[rt]+=c*cc[rt];
        return ;
    }
    DOWN(rt);
    int mid=(l+r)>>1;
    upd(L,R,c,lson);upd(L,R,c,rson);
}
ll qry(int p,int l,int r,int rt) {
    if(p<l||p>r) return 0;
    if(l==r) return ss[rt];
    int mid=(l+r)>>1;
    DOWN(rt);
    return qry(p,lson)+qry(p,rson);
}
int main(){
    int T;scanf("%d",&T);
    while(T--) {
        ///
        scanf("%d",&n);
        ///init
        rep(i,0,n+1) G[i].clear();
        init();
        build(1,n,1);
        ///read
        rep(i,1,n+1) {
            scanf("%d",v+i);
            a[i].fi=-v[i];
            a[i].se=i;
        }
        rep(i,1,n) {
            int u,v;scanf("%d%d",&u,&v);
            G[u].pb(v);
            G[v].pb(u);
        }
        ///solve
        dfs1(1,1,1);
        dfs2(1,1);
        sort(a+1,a+1+n);
        rep(i,1,n+1) {
            int val=-a[i].fi;
            int ind=a[i].se;
            for(;;) {
                upd(tid[top[ind]],tid[ind],val,1,n,1);
                if(top[ind]==1) break;
                ind=fa[top[ind]];
            }
        }
        ///print
        rep(i,1,n+1) printf("%lld ",qry(tid[i],1,n,1));
        puts("");
    }
    return 0;
}