垃圾题。
下午心态爆炸。快哭了。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> using namespace std; typedef long long LL; struct trnode { int l,r,lc,rc,id;LL c,lazy; }tr[410000];int trlen; void bt(int l,int r) { trlen++;int now=trlen; tr[now].l=l;tr[now].r=r; tr[now].c=0;tr[now].id=0; tr[now].lazy=0; if(l==r) tr[now].lc=tr[now].rc=-1; else { int mid=(l+r)/2; tr[now].lc=trlen+1;bt(l,mid); tr[now].rc=trlen+1;bt(mid+1,r); } } void change(int now,int l,int r,LL k,int id) { if(tr[now].l==l&&tr[now].r==r) { tr[now].c+=k;tr[now].lazy+=k; if(id!=0)tr[now].id=id; return ; } int lc=tr[now].lc,rc=tr[now].rc; int mid=(tr[now].l+tr[now].r)/2; if(tr[now].lazy!=0) { tr[lc].c+=tr[now].lazy; tr[rc].c+=tr[now].lazy; tr[lc].lazy+=tr[now].lazy; tr[rc].lazy+=tr[now].lazy; tr[now].lazy=0; } if(r<=mid) change(lc,l,r,k,id); else if(mid+1<=l)change(rc,l,r,k,id); else change(lc,l,mid,k,id), change(rc,mid+1,r,k,id); if(tr[lc].c>tr[rc].c) tr[now].c=tr[lc].c, tr[now].id=tr[lc].id; else tr[now].c=tr[rc].c, tr[now].id=tr[rc].id; } //--------seq_tree------------------------------------------- LL c[410000]; struct node { int x,y,next; }a[410000];int len,last[410000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int z,l[410000],r[410000]; int fa[410000]; void dfs(int x,LL sum) { if(last[x]==0) { z++; l[x]=z;r[x]=z; change(1,l[x],r[x],sum,x); } for(int k=last[x];k;k=a[k].next) { int y=a[k].y; fa[y]=x; dfs(y,sum+c[y]); if(k==last[x])l[x]=l[y]; r[x]=r[y]; } } bool v[410000]; int main() { int n,K,x,y; scanf("%d%d",&n,&K); for(int i=1;i<=n;i++)scanf("%lld",&c[i]); len=0;memset(last,0,sizeof(last)); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); ins(x,y);fa[y]=x; } bt(1,n); dfs(1,c[1]); LL ans=0; memset(v,false,sizeof(v)); while(K--) { ans+=tr[1].c; x=tr[1].id; while(x!=0) { if(v[x]==false) { change(1,l[x],r[x],-c[x],0); v[x]=true; x=fa[x]; } else break; } } printf("%lld ",ans); return 0; }