【模板】轻重链部分过了,这题过不去!
查看原帖
【模板】轻重链部分过了,这题过不去!
173660
zhoukangyang楼主2020/5/23 11:09
#include<bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
int n,m,sum[N<<2],lazy[N<<2],siz[N],idd[N],heavy[N],fa[N],maxto[N],dep[N],fir[N],tot;
int head[N],last[N];
struct node {
    int to,next;
} e[N<<1];
void add_edge(int l,int r,int id) {
    if(head[l]==0) head[l]=id;
    else e[last[l]].next=id;
    last[l]=id,e[id].to=r;
}
void add(int L,int R,int l,int r,int id,int k) {
    int mid=(L+R)/2;
    sum[id] = (sum[id]+(r-l+1)*k);
    if(l==L&&r==R) lazy[id] = (lazy[id]+k);
    else if(r <= mid) add(L,mid,l,r,id*2,k);
    else if(l >  mid) add(mid+1,R,l,r,id*2+1,k);
    else add(L,mid,l,mid,id*2,k),add(mid+1,R,mid+1,r,id*2+1,k);
}
int gsum(int L,int R,int l,int r,int id) {
    int mid=(L+R)/2,kkk=(r-l+1)*lazy[id];
    if(l==L&&r==R) return sum[id];
    if(r <= mid) return (kkk+gsum(L,mid,l,r,id*2));
    if(l >  mid) return (kkk+gsum(mid+1,R,l,r,id*2+1));
    return (kkk+gsum(L,mid,l,mid,id*2)+gsum(mid+1,R,mid+1,r,id*2+1));
} 
void dfsa(int x) {
    siz[x]=1,dep[x]=dep[fa[x]]+1;
    int maxn = 0;
    for(int i = head[x]; i != 0; i = e[i].next) {
        if(e[i].to==fa[x]) continue;
        fa[e[i].to]=x,dfsa(e[i].to),siz[x] += siz[e[i].to];
        if(siz[e[i].to]>maxn) heavy[x]=e[i].to,maxn=siz[e[i].to];
    }
}
void dfsb(int x) {
    ++tot,idd[x]=tot;
    if(maxto[x]==0) maxto[x]=x;
    if(siz[x]==1) return;
    maxto[heavy[x]]=maxto[x],dfsb(heavy[x]);
    for(int i = head[x]; i != 0; i = e[i].next) {
        if(e[i].to==fa[x]||e[i].to==heavy[x]) continue;
        dfsb(e[i].to);
    }
}
signed main() {
    int u,v,k,opt,Ans;
    scanf("%lld%lld",&n,&m);
    for(int i = 1; i <= n; i++) scanf("%lld",&fir[i]);
    for(int i = 1; i < n; i++) scanf("%lld%lld",&u,&v),add_edge(u,v,i*2-1),add_edge(v,u,i*2);
    fa[1]=1,dfsa(1),dfsb(1);
    for(int i = 1; i <= n; i++) add(1,n,idd[i],idd[i],1,fir[i]);
    while(m--) {
        scanf("%lld",&opt);
        if(opt==1) {
            scanf("%lld%lld",&u,&k);
            add(1,n,idd[u],idd[u],1,k);
        }
        if(opt==2) {
            scanf("%lld%lld",&u,&k);
            while(maxto[u]!=1) {
                add(1,n,idd[maxto[u]],idd[u],1,k);
                u = fa[maxto[u]];
            }
            add(1,n,1,idd[u],1,k);
        }
        if(opt==3) {
        	Ans=0;
            scanf("%lld",&u);
            while(maxto[u]!=1) {
                Ans += gsum(1,n,idd[maxto[u]],idd[u],1);
                u = fa[maxto[u]];
            }
            Ans += gsum(1,n,1,idd[u],1);
            printf("%lld\n",Ans);
        }
    }
    return 0;
}
2020/5/23 11:09
加载中...