P10163 [DTCPC 2024] 平方树题目描述给你一个森林每条边有一个方向。你可以进行两种操作新增一个点。将两个点之间连一条有向边。你要使得最后将所有有向边看成无向边后图形成一棵树且每个点的出度都是平方数。给出一种新增点数最少的方案。输入格式第一行两个整数n,mn,mn,m1≤mn≤1051\le m \lt n \le 10^51≤mn≤105表示这个森林的点数和边数。接下来mmm行每行两个数u,vu,vu,v1≤u,v≤n1\le u,v\le n1≤u,v≤n表示一条uuu连向vvv的有向边。保证将每条边看作无向边后这张图是森林。输出格式第一行两个整数x,yx,yx,y表示你的新增点数和连边数。接下来yyy行每行两个数u,vu,vu,v表示新增一条uuu连向vvv的有向边你要保证1≤u,v≤nx1\le u,v\le nx1≤u,v≤nx。输入输出样例 #1输入 #13 2 1 2 1 3输出 #12 2 1 4 1 5思路直接写即可。代码#includebits/stdc.husingnamespacestd;longlongn,m,uu,vv2,fa[1000006],u[1000006],oi[1005],uo[1000006],ok[1000006],oc0,ov0,hu[1000006],ku[1000006],ih0,op0,ik0;vectorlonglongv[100005],vv[100005];structone{longlongx,y;}a[1000006];longlongfind(longlonga1){if(a1fa[a1]){returna1;}else{fa[a1]find(fa[a1]);returnfa[a1];}}longlongcn2(longlonga1){longlongl0,r1000,md1001;while(lr){longlongmid(lr)/2;if(oi[mid]a1){mdmin(md,mid);rmid-1;}else{lmid1;}}returnoi[md]-a1;}intmain(){cinnm;for(inti1;i1000000;i){fa[i]i;}for(inti0;i1001;i){oi[i]i*i;}for(inti1;im;i){cinuuvv2;v[uu].push_back(vv2);u[uu];if(find(uu)!find(vv2)){fa[find(vv2)]find(uu);}vv[uu].push_back(vv2);vv[vv2].push_back(uu);}for(inti1;in;i){uo[i]cn2(u[i]);// couti u[i] uo[i]endl;ovuo[i];if(uo[i]!0){ku[ik]i;}}for(inti1;in;i){if(fa[i]i){ok[oc]i;}}if(ocov){while(oc2){longlonga1find(ok[oc]),b1find(ok[oc-1]),c1ku[ik];if(uo[c1]0){ik--;c1ku[ik-1];}if(find(c1)!a1){a[ih](one){c1,a1};fa[a1]find(c1);uo[c1]--;oc--;}else{a[ih](one){c1,b1};fa[b1]find(c1);uo[c1]--;oc--;ok[oc]ok[oc1];}}for(inti1;iik;i){for(intj1;juo[ku[i]];j){a[ih](one){ku[i],n(op)};}}coutop ihendl;for(inti1;iih;i){couta[i].x a[i].yendl;}}else{ov0;ik0;for(inti1;in;i){uo[i]cn2(u[i]);// couti u[i] uo[i]endl;if(u[i]0){ku[ik]i;}}for(inti1;in;i){uo[i]cn2(u[i]);// couti u[i] uo[i]endl;ovuo[i];if(uo[i]!0){ku[ik]i;}if(u[i]0){uo[i]1;}}while(oc2){longlonga1find(ok[oc]),b1find(ok[oc-1]),c1ku[ik];if(uo[c1]0){ik--;c1ku[ik-1];}if(find(c1)!a1){a[ih](one){c1,a1};fa[a1]find(c1);uo[c1]--;oc--;}else{a[ih](one){c1,b1};fa[b1]find(c1);uo[c1]--;oc--;ok[oc]ok[oc1];}}coutop ihendl;for(inti1;iih;i){couta[i].x a[i].yendl;}}return0;}