題目大意：給你一棵樹，讓你對(duì)葉節(jié)點(diǎn)分組，保證每組中，任意兩個(gè)葉節(jié)點(diǎn)之間的距離不大于K，求最小的組數(shù)

手動(dòng)yy的貪心竟然對(duì)的

對(duì)于每個(gè)節(jié)點(diǎn)，維護(hù)一個(gè)$ma[i]$，表示在$i$節(jié)點(diǎn)的子樹內(nèi) 未被分組的葉節(jié)點(diǎn)到$i$節(jié)點(diǎn)的最長(zhǎng)距離

那么，對(duì)于每個(gè)節(jié)點(diǎn)，把它的子節(jié)點(diǎn)按照$ma[i]$排序，那么如果這個(gè)點(diǎn)的子樹不需要額外的分組，就要保證最大的$ma[v1]$和次大的$ma[v2]$之間的距離小于等于K

如果不滿足，說明需要對(duì)子樹內(nèi)的節(jié)點(diǎn)進(jìn)行額外分組

根據(jù)貪心的思想，選擇ma最大的子節(jié)點(diǎn)$v1$，那么就從小往大一直找滿足$ma[v1]+ma[vj]<=K$的點(diǎn)，當(dāng)不滿足條件時(shí)，說明剛才找過的小節(jié)點(diǎn)和那個(gè)較大的節(jié)點(diǎn)可以分成一組。接下來，要看次大$v2$的點(diǎn)能否滿足更次大$v3$能否滿足$ma[v2]+ma[v3]<=K$，找到說明可行，回溯。否則要繼續(xù)剛才的過程，直到剩余子節(jié)點(diǎn)之間的最長(zhǎng)距離<=K

因?yàn)槊總€(gè)節(jié)點(diǎn)只會(huì)以這種方式被遍歷到一次，所以并不需要二分

1號(hào)節(jié)點(diǎn)可能是葉節(jié)點(diǎn)，所以不能直接把1當(dāng)成根

另外，如果根節(jié)點(diǎn)的ma>1，說明根節(jié)點(diǎn)還剩下一些節(jié)點(diǎn)沒被分組，把它們分到一組即可

1 #include <vector> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #define ll long long 6 #define N 1001000 7 #define uint unsigned int 8 #define inf 0x3f3f3f3f3f3f3fll 9 using namespace std; 10 //re 11 int gint() 12 { 13 int ret=0,fh=1;char c=getchar(); 14 while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();} 15 while(c>='0'&&c<='9'){ret=(ret<<3)+(ret<<1)+c-'0';c=getchar();} 16 return ret*fh; 17 } 18 19 int n,m,cte,num,S; 20 int head[N],fa[N],inc[N]; 21 struct Edge{int to,nxt;}edge[N*2]; 22 23 void ae(int u,int v){ 24 cte++;edge[cte].to=v,inc[v]++; 25 edge[cte].nxt=head[u],head[u]=cte; 26 } 27 28 vector<int>to[N]; 29 int ma[N]; 30 int cmp(int x,int y){return ma[x]<ma[y];} 31 int solve(int u){ 32 int ans=0,l,r; 33 for(int j=head[u];j;j=edge[j].nxt) 34 { 35 int v=edge[j].to; 36 if(v==fa[u]) continue; 37 to[u].push_back(v); 38 ans+=solve(v); 39 } 40 int tot=to[u].size(); 41 sort(to[u].begin(),to[u].end(),cmp); 42 if(!tot){ma[u]=1;return 0;} 43 if(tot==1){ma[u]=ma[to[u][tot-1]];} 44 else if(ma[to[u][tot-1]]+ma[to[u][tot-2]]<=m) 45 ma[u]=ma[to[u][tot-1]]; 46 else{ 47 l=0,r=tot-1; 48 while(r>0&&l<r&&ma[to[u][r]]+ma[to[u][r-1]]>m){ 49 for(;l<r&&ma[to[u][r]]+ma[to[u][l]]<=m;l++); 50 r--,ans++; 51 }ma[u]=ma[to[u][r]]; 52 }ma[u]+=(ma[u]>0?1:0);return ans; 53 } 54 55 56 int main() 57 { 58 scanf("%d%d",&n,&m); 59 int x,y; 60 for(int i=1;i<n;i++) 61 x=gint(),y=gint(),ae(x,y),ae(y,x); 62 for(int i=1;i<=n;i++) 63 if(inc[i]!=1) {S=i;break;} 64 dep[S]=1,dfs1(S,-1); 65 tp[S]=1,dfs2(S); 66 int ans=solve(S); 67 if(ma[S]-1>0) ans++; 68 printf("%d\n",ans); 69 return 0; 70 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/guapisolo/p/9812742.html

總結(jié)

以上是生活随笔為你收集整理的CF1042F Leaf Sets (贪心+树上构造)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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