bzoj 3252 攻略

题目大意：

树上每个点有一个正的点权，选k条从根出发的的链使链并权值和最大

思路：

被长链剖分的标签骗进来

法1：

这道题长链剖分标签的由来，类似重链剖分把树剖成若干条链，然后贪心的选k条即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #define ll long long
12 #define inf 2139062143
13 #define MAXN 200100
14 #define MOD 998244353
15 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)
16 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)
17 #define ren for(register int i=fst[x];i;i=nxt[i])
18 #define pb(i,x) vec[i].push_back(x)
19 #define pls(a,b) (a+b)%MOD
20 #define mns(a,b) (a-b+MOD)%MOD
21 #define mul(a,b) (1LL*(a)*(b))%MOD
22 using namespace std;
23 inline int read()
24 {
25     int x=0,f=1;char ch=getchar();
26     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
27     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
28     return x*f;
29 }
30 int n,m,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],val[MAXN];
31 int mxs[MAXN],bl[MAXN],cnt;ll ans,mxd[MAXN];
32 priority_queue <ll> q;
33 void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
34 void dfs(int x,int pa)
35 {
36     ren if(to[i]^pa)
37     {
38         dfs(to[i],x);
39         if(mxd[to[i]]>mxd[mxs[x]]) mxs[x]=to[i];
40     }
41     mxd[x]=mxd[mxs[x]]+val[x];
42 }
43 void dfs(int x,int pa,int anc)
44 {
45     bl[x]=anc;if(mxs[x]) dfs(mxs[x],x,anc);
46     ren if(to[i]^pa&&to[i]^mxs[x]) dfs(to[i],x,to[i]);
47 }
48 int main()
49 {
50     n=read(),m=read();int a,b;rep(i,1,n) val[i]=read();
51     rep(i,2,n) a=read(),b=read(),add(a,b),add(b,a);
52     dfs(1,0);dfs(1,0,1);rep(i,1,n) if(bl[i]==i) q.push(mxd[i]);a=1;
53     while(a<=m&&!q.empty()) {ans+=q.top();q.pop();a++;}
54     printf("%lld
",ans);
55 }

View Code

法2：

依然是贪心，只不过在过程中使用可并堆来维护

每次把这个点的权值加到堆顶即可（需要注意只有堆中只有叶子节点

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #define ll long long
12 #define inf 2139062143
13 #define MAXN 200100
14 #define MOD 998244353
15 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)
16 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)
17 #define ren for(register int i=fst[x];i;i=nxt[i])
18 #define pb(i,x) vec[i].push_back(x)
19 #define pls(a,b) (a+b)%MOD
20 #define mns(a,b) (a-b+MOD)%MOD
21 #define mul(a,b) (1LL*(a)*(b))%MOD
22 using namespace std;
23 inline int read()
24 {
25     int x=0,f=1;char ch=getchar();
26     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
27     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
28     return x*f;
29 }
30 int n,m,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],cnt,ind[MAXN];
31 int rt[MAXN],ls[MAXN],rs[MAXN],dis[MAXN],val[MAXN];
32 ll ans,v[MAXN];
33 void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,ind[v]++;}
34 int merge(int x,int y)
35 {
36     if(!(x*y)) return x|y;if(v[x]<v[y]) swap(x,y);
37     rs[x]=merge(rs[x],y);if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
38     dis[x]=dis[rs[x]]+1;return x;
39 }
40 void dfs(int x,int pa)
41 {
42     if(ind[x]==1) rt[x]=x;ren if(to[i]^pa)
43         {dfs(to[i],x);rt[x]=merge(rt[x],rt[to[i]]);}
44     v[rt[x]]+=val[x];
45 }
46 int main()
47 {
48     n=read(),m=read();int a,b;rep(i,1,n) val[i]=read();
49     rep(i,2,n) a=read(),b=read(),add(a,b),add(b,a);
50     dfs(1,0);
51     while(m--) {ans+=v[rt[1]];rt[1]=merge(ls[rt[1]],rs[rt[1]]);}
52     printf("%lld
",ans);
53 }

View Code