BZOJ3252

長(zhǎng)鏈剖分之后把每條長(zhǎng)鏈拿出來然后排個(gè)序選就完了

Code：

#include<bits/stdc++.h> #define ll long long using namespace std; inline int read(){int res=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}return res*f; } const int N=2e5+5; int vis[N<<1],nxt[N<<1],head[N<<1],tot=0; int val[N],fa[N],lson[N],top[N]; inline void add(int x,int y){vis[++tot]=y;nxt[tot]=head[x];head[x]=tot;} ll ans,md[N]; void dfs1(int v){md[v]=val[v];for(int i=head[v];i;i=nxt[i]){int y=vis[i];if(y==fa[v]) continue;fa[y]=v;dfs1(y);md[v]=max(md[v],md[y]+val[v]);if(md[y]>md[lson[v]]) lson[v]=y;} } void dfs2(int v){top[v]=v==lson[fa[v]]?top[fa[v]]:v;if(lson[v]) dfs2(lson[v]);for(int i=head[v];i;i=nxt[i])if(!top[vis[i]]) dfs2(vis[i]); } int n,m; priority_queue<ll>q; int main(){n=read(),m=read();for(int i=1;i<=n;i++) val[i]=read();for(int x,y,i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);dfs1(1);top[1]=1;dfs2(1);for(int i=1;i<=n;i++) if(top[i]==i) q.push(md[i]);int j=1;while(!q.empty() && j<=m){ans+=q.top();q.pop();++j;}cout<<ans<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的[BZOJ3252][长链剖分]攻略的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。