阿里云建站论坛网站,方维网络的品牌网站建设,建站快车优势,淘宝网站设计价格题目大意#xff1a;给你一棵树#xff0c;让你对叶节点分组#xff0c;保证每组中#xff0c;任意两个叶节点之间的距离不大于K#xff0c;求最小的组数 手动yy的贪心竟然对的 对于每个节点#xff0c;维护一个$ma[i]$#xff0c;表示在$i$节点的子树内 未被分组的叶节…题目大意给你一棵树让你对叶节点分组保证每组中任意两个叶节点之间的距离不大于K求最小的组数 手动yy的贪心竟然对的 对于每个节点维护一个$ma[i]$表示在$i$节点的子树内 未被分组的叶节点到$i$节点的最长距离 那么对于每个节点把它的子节点按照$ma[i]$排序那么如果这个点的子树不需要额外的分组就要保证最大的$ma[v1]$和次大的$ma[v2]$之间的距离小于等于K 如果不满足说明需要对子树内的节点进行额外分组 根据贪心的思想选择ma最大的子节点$v1$那么就从小往大一直找满足$ma[v1]ma[vj]K$的点当不满足条件时说明刚才找过的小节点和那个较大的节点可以分成一组。接下来要看次大$v2$的点能否满足更次大$v3$能否满足$ma[v2]ma[v3]K$找到说明可行回溯。否则要继续刚才的过程直到剩余子节点之间的最长距离K 因为每个节点只会以这种方式被遍历到一次所以并不需要二分 1号节点可能是叶节点所以不能直接把1当成根 另外如果根节点的ma1说明根节点还剩下一些节点没被分组把它们分到一组即可 1 #include vector2 #include cstdio3 #include algorithm4 #include cstring5 #define ll long long6 #define N 10010007 #define uint unsigned int8 #define inf 0x3f3f3f3f3f3f3fll9 using namespace std;
10 //re
11 int gint()
12 {
13 int ret0,fh1;char cgetchar();
14 while(c0||c9){if(c-)fh-1;cgetchar();}
15 while(c0c9){ret(ret3)(ret1)c-0;cgetchar();}
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].tov,inc[v];
25 edge[cte].nxthead[u],head[u]cte;
26 }
27
28 vectorintto[N];
29 int ma[N];
30 int cmp(int x,int y){return ma[x]ma[y];}
31 int solve(int u){
32 int ans0,l,r;
33 for(int jhead[u];j;jedge[j].nxt)
34 {
35 int vedge[j].to;
36 if(vfa[u]) continue;
37 to[u].push_back(v);
38 anssolve(v);
39 }
40 int totto[u].size();
41 sort(to[u].begin(),to[u].end(),cmp);
42 if(!tot){ma[u]1;return 0;}
43 if(tot1){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 l0,rtot-1;
48 while(r0lrma[to[u][r]]ma[to[u][r-1]]m){
49 for(;lrma[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 i1;in;i)
61 xgint(),ygint(),ae(x,y),ae(y,x);
62 for(int i1;in;i)
63 if(inc[i]!1) {Si;break;}
64 dep[S]1,dfs1(S,-1);
65 tp[S]1,dfs2(S);
66 int anssolve(S);
67 if(ma[S]-10) ans;
68 printf(%d\n,ans);
69 return 0;
70 } 转载于:https://www.cnblogs.com/guapisolo/p/9812742.html
