BZOJ 3252: 攻略(思路题)

传送门

解题思路

　　比较好想的一道思路题，结果有个地方没开\(long\) \(long\) \(wa\)了三次。。其实就是模仿一下树链剖分，重新定义重儿子，一个点的重儿子为所有儿子中到叶节点权值最大的点，然后就和树链剖分一样\(dfs\)一遍，把那些链的顶端的\(sum\)值放到一个数组排个序。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>using namespace std;
const int MAXN = 200005;
typedef long long LL;inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return f?x:-x;
}int n,k,head[MAXN],cnt,to[MAXN],nxt[MAXN],fa[MAXN];
int w[MAXN],son[MAXN],num;
LL ans,sum[MAXN],tmp[MAXN];inline void add(int bg,int ed){
to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}inline bool cmp(LL x,LL y){
return x>y;
}void dfs1(int x){
LL maxson=0,u;sum[x]=w[x];
for(int i=head[x];i;i=nxt[i]){
u=to[i];dfs1(u);
if(sum[u]>maxson) {maxson=sum[u];son[x]=u;}
}
sum[x]+=maxson;
}signed main(){
n=rd(),k=rd();int x,y;
for(int i=1;i<=n;i++) w[i]=rd();
for(int i=1;i<n;i++){
x=rd(),y=rd();fa[y]=x;
add(x,y);
}
dfs1(1);
for(int i=1;i<=n;i++) if(i!=son[fa[i]]) tmp[++num]=sum[i];
sort(tmp+1,tmp+1+num,cmp);
for(int i=1;i<=k;i++) ans+=tmp[i];
printf("%lld\n",ans);
return 0;
}