A.Cat
题意：
每次询问给出，要求找一个最长的连续区间
，满足
。
题解：
因为,
为非负整数
所以我们只要暴力枚举一下头部和尾部即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fll;
const int mod = 998244353;
ll gao(ll l, ll r)
{
if (l > r)
return INFL;
ll res = 0;
if (r - l + 1 <= 10)
{
for (ll i = l; i <= r; i++)
res ^= i;
}
else
{
ll ql = l, qr = r;
while ((ql % 4) != 0)
{
res ^= ql;
ql++;
}
while ((qr % 4) != 3)
{
res ^= qr;
qr--;
}
}
return res;
}
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
{
ll L, R, S;
scanf("%lld%lld%lld", &L, &R, &S);
ll res = -1;
for (int i = 0; i <= 4; i++)
for (int j = 0; j <= 4; j++)
{
ll tmp = gao(L + i, R - j);
if (tmp <= S)
res = max(res, (R - j) - (L + i) + 1);
}
printf("%lld\n", res);
}
return 0;
} C.<3 numbers
题意：
记为区间
内素数个数，每次询问给出
，判断
是否成立
题解：
由素数的分布可知，当区间较大时素数密度一定小于三分之一，当区间较小时暴力判断即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fll;
const int mod = 998244353;
bool flag[maxn];
int prime[maxn], top;
void getPrime()
{
int i, j;
for (i = 2; i < maxn; i++)
{
if (!flag[i])
prime[top++] = i;
for (j = 0; j < top && i * prime[j] < maxn; j++)
{
flag[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
}
bool isprime(int x)
{
if (x < maxn)
return !flag[x];
for (int i = 2; 1ll * i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
bool judge(int l, int r)
{
int tot = r - l + 1;
int num = 0;
for (int i = l; i <= r; i++)
{
if (isprime(i))
num++;
}
return 3 * num < tot;
}
int main()
{
getPrime();
int t;
for (scanf("%d", &t); t >= 1; t--)
{
ll L, R;
scanf("%lld%lld", &L, &R);
if (R - L + 1 > 60)
puts("Yes");
else
puts(judge(L, R) ? "Yes" : "No");
}
return 0;
} E.Multiply(Pollard-Rho)
题意：
给出个数
，令
现在给出,
，它想要一个最大的
，使得
是
的因子
题解：
先对进行分解得到它的所有素因子及幂次。
然后找出其每个因子在中还剩多少个。
对每个因子用幂次除以的结果就是其结果，取最小值即可
其中X较大，用常规的分解质因数复杂度太高，故用Pollard-Rho
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n;
ll x, y, a[N];
mt19937 rd(time(0));
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll mul(ll a, ll b, ll p)
{
return (a * b - (ll)(a / (long double)p * b + 1e-3) * p + p) % p;
}
ll qpow(ll base, ll n, ll p)
{
ll res = 1;
base %= p;
while (n)
{
if (n & 1)
res = mul(res, base, p);
base = mul(base, base, p);
n >>= 1;
}
return res;
}
struct Mill
{
ll n, fac[22000][2], bk[22000];
int tot;
const int C = 2307; //findfac随机设置的一个数
const int S = 8; //miller_rabin测试重复次数
bool check(ll a, ll n)
{
ll m = n - 1, x, y = 0;
int j = 0;
while (!(m & 1)) //将n-1分解成2^j*m
{
m >>= 1;
++j;
}
x = qpow(a, m, n);
for (int i = 1; i <= j; x = y, ++i)
{
y = mul(x, x, n);
if (y == 1 && x != 1 && x != n - 1)
return 1;
}
return y != 1; //费马小定理
}
bool miller_rabin(ll n)
{
//特判
if (n < 2)
return 0;
else if (n == 2)
return 1;
else if (!(n & 1)) //偶数
return 0;
for (int i = 0; i < S; ++i) //重复S次
if (check(rd() % (n - 1) + 1, n))
return 0;
return 1;
}
ll pollard_rho(ll n, int c) //找到n的一个因子
{
ll i = 1, k = 2, x = rd() % n, y = x, d;
while (1)
{
++i;
x = (mul(x, x, n) + c) % n; //不断调整x2
d = gcd(y - x, n);
if (d > 1 && d < n)
return d; //找到因子
if (y == x)
return n; //找到循环，返回n，重新来
if (i == k) //一个优化
{
y = x;
k <<= 1;
}
}
}
void findfac(ll n, int c)
{
if (n == 1) //递归出口
return;
if (miller_rabin(n)) //如果是素数，就加入
{
bk[++*bk] = n;
return;
}
ll m = n;
while (m == n)
m = pollard_rho(n, c--); //不断找因子，直到找到为止，返回n说明没找到
findfac(m, c);
findfac(n / m, c);
}
void gao(ll _n)
{
n = _n;
*bk = 0;
findfac(n, C);
sort(bk + 1, bk + 1 + *bk);
fac[1][0] = bk[1];
fac[1][1] = 1;
tot = 1;
for (int i = 2; i <= *bk; ++i)
{
if (bk[i] == bk[i - 1])
++fac[tot][1];
else
{
++tot;
fac[tot][0] = bk[i];
fac[tot][1] = 1;
}
}
}
} mill;
ll cal(ll n, ll x) //计算n!中质因子x的数量
{
ll num = 0;
while (n)
{
num += n / x;
n = n / x;
}
return num;
}
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
{
scanf("%d%lld%lld", &n, &x, &y);
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
mill.gao(x);
int tot = mill.tot;
ll res = 8e18;
for (int i = 1; i <= tot; ++i)
{
ll num = 0;
for (int j = 1; j <= n; j++)
num += cal(a[j], mill.fac[i][0]);
res = min(1ll * res, (cal(y, mill.fac[i][0]) - num) / mill.fac[i][1]);
}
printf("%lld\n", res);
}
return 0;
} F.The Answer to the Ultimate Question of Life, The Universe, and Everything.
题意：
每次询问给出，需要找出
,
,
,其中
满足
题解：
观察到的范围只有200，并且
,
,
范围也不大，所以直接打表
打表代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ok(ll need)
{
ll l = -5000, r = 5000, res = -12345678;
while (r - l >= 0)
{
ll mid = (l + r) >> 1;
ll tmp = mid * mid * mid;
if (tmp == need)
return mid;
if (tmp > need)
r = mid - 1;
else
l = mid + 1;
}
return res;
}
bool gao(int x)
{
int limit = 5000;
for (ll a = -limit; a <= limit; ++a)
for (ll b = -limit; b <= limit; ++b)
{
ll need = 1ll * x - a * a * a - b * b * b;
ll c = ok(need);
if (abs(c) <= 5000)
{
cout << a << " " << b << " " << c << endl;
printf("ans[%d].x=%d;ans[%d].y=%d;ans[%d].z=%d;\n",x,a,x,b,x,c);
return true;
}
}
return false;
}
int main()
{
freopen("out.txt","r",stdout);
for (int i = 0; i <= 200; ++i)
gao(i);
return 0;
} AC代码：
#include<bits/stdc++.h>
#define inf 6666
using namespace std;
typedef long long ll;
const int N=205;
struct node
{
int x,y,z;
node(){x=y=z=inf;}
}ans[N];
int main()
{
ans[0].x=0;ans[0].y=5000;ans[0].z=-5000;
ans[1].x=1;ans[1].y=5000;ans[1].z=-5000;
ans[2].x=-486;ans[2].y=4375;ans[2].z=-4373;
ans[3].x=4;ans[3].y=4;ans[3].z=-5;
ans[6].x=-205;ans[6].y=644;ans[6].z=-637;
ans[7].x=44;ans[7].y=168;ans[7].z=-169;
ans[8].x=2;ans[8].y=5000;ans[8].z=-5000;
ans[9].x=-52;ans[9].y=217;ans[9].z=-216;
ans[10].x=-353;ans[10].y=683;ans[10].z=-650;
ans[11].x=-641;ans[11].y=843;ans[11].z=-695;
ans[12].x=7;ans[12].y=10;ans[12].z=-11;
ans[15].x=-262;ans[15].y=332;ans[15].z=-265;
ans[16].x=-588;ans[16].y=4118;ans[16].z=-4114;
ans[17].x=2195;ans[17].y=2977;ans[17].z=-3331;
ans[18].x=-1276;ans[18].y=1671;ans[18].z=-1373;
ans[19].x=47;ans[19].y=91;ans[19].z=-95;
ans[20].x=-741;ans[20].y=2833;ans[20].z=-2816;
ans[21].x=-287;ans[21].y=445;ans[21].z=-401;
ans[24].x=8;ans[24].y=8;ans[24].z=-10;
ans[25].x=1839;ans[25].y=2357;ans[25].z=-2683;
ans[26].x=237;ans[26].y=2106;ans[26].z=-2107;
ans[27].x=3;ans[27].y=5000;ans[27].z=-5000;
ans[28].x=-249;ans[28].y=2269;ans[28].z=-2268;
ans[29].x=-69;ans[29].y=235;ans[29].z=-233;
ans[34].x=-244;ans[34].y=1557;ans[34].z=-1555;
ans[35].x=-509;ans[35].y=1154;ans[35].z=-1120;
ans[36].x=2358;ans[36].y=2731;ans[36].z=-3223;
ans[37].x=-84;ans[37].y=445;ans[37].z=-444;
ans[38].x=16;ans[38].y=25;ans[38].z=-27;
ans[43].x=-307;ans[43].y=837;ans[43].z=-823;
ans[44].x=-5;ans[44].y=8;ans[44].z=-7;
ans[45].x=1709;ans[45].y=2025;ans[45].z=-2369;
ans[46].x=-473;ans[46].y=815;ans[46].z=-758;
ans[47].x=49;ans[47].y=139;ans[47].z=-141;
ans[48].x=-1247;ans[48].y=3991;ans[48].z=-3950;
ans[51].x=602;ans[51].y=659;ans[51].z=-796;
ans[53].x=1518;ans[53].y=2141;ans[53].z=-2370;
ans[54].x=-648;ans[54].y=3891;ans[54].z=-3885;
ans[55].x=1837;ans[55].y=3131;ans[55].z=-3329;
ans[56].x=505;ans[56].y=559;ans[56].z=-672;
ans[57].x=361;ans[57].y=982;ans[57].z=-998;
ans[60].x=-163;ans[60].y=1202;ans[60].z=-1201;
ans[61].x=668;ans[61].y=845;ans[61].z=-966;
ans[62].x=-1561;ans[62].y=2903;ans[62].z=-2744;
ans[63].x=102;ans[63].y=146;ans[63].z=-161;
ans[64].x=4;ans[64].y=5000;ans[64].z=-5000;
ans[65].x=403;ans[65].y=903;ans[65].z=-929;
ans[66].x=1;ans[66].y=4;ans[66].z=1;
ans[69].x=134;ans[69].y=398;ans[69].z=-403;
ans[70].x=824;ans[70].y=2325;ans[70].z=-2359;
ans[71].x=401;ans[71].y=443;ans[71].z=-533;
ans[72].x=-104;ans[72].y=434;ans[72].z=-432;
ans[73].x=-146;ans[73].y=344;ans[73].z=-335;
ans[78].x=-829;ans[78].y=2123;ans[78].z=-2080;
ans[79].x=-196;ans[79].y=711;ans[79].z=-706;
ans[80].x=-706;ans[80].y=1366;ans[80].z=-1300;
ans[81].x=-1719;ans[81].y=2638;ans[81].z=-2368;
ans[82].x=847;ans[82].y=1188;ans[82].z=-1317;
ans[83].x=1315;ans[83].y=3651;ans[83].z=-3707;
ans[87].x=-1972;ans[87].y=4271;ans[87].z=-4126;
ans[88].x=-1282;ans[88].y=1686;ans[88].z=-1390;
ans[89].x=1953;ans[89].y=2036;ans[89].z=-2514;
ans[90].x=365;ans[90].y=1798;ans[90].z=-1803;
ans[91].x=-2912;ans[91].y=3992;ans[91].z=-3389;
ans[92].x=861;ans[92].y=4039;ans[92].z=-4052;
ans[93].x=-98;ans[93].y=253;ans[93].z=-248;
ans[96].x=14;ans[96].y=20;ans[96].z=-22;
ans[97].x=-991;ans[97].y=3200;ans[97].z=-3168;
ans[98].x=-1638;ans[98].y=2391;ans[98].z=-2101;
ans[99].x=-622;ans[99].y=984;ans[99].z=-893;
ans[100].x=-903;ans[100].y=1870;ans[100].z=-1797;
ans[101].x=319;ans[101].y=2325;ans[101].z=-2327;
ans[102].x=118;ans[102].y=229;ans[102].z=-239;
ans[105].x=-4;ans[105].y=8;ans[105].z=-7;
ans[106].x=-1165;ans[106].y=2760;ans[106].z=-2689;
ans[107].x=947;ans[107].y=1117;ans[107].z=-1309;
ans[108].x=-948;ans[108].y=1345;ans[108].z=-1165;
ans[109].x=853;ans[109].y=2924;ans[109].z=-2948;
ans[111].x=-2312;ans[111].y=4966;ans[111].z=-4793;
ans[115].x=8;ans[115].y=11;ans[115].z=-12;
ans[116].x=-757;ans[116].y=1945;ans[116].z=-1906;
ans[117].x=-555;ans[117].y=962;ans[117].z=-896;
ans[118].x=383;ans[118].y=4327;ans[118].z=-4328;
ans[119].x=-1673;ans[119].y=3789;ans[119].z=-3677;
ans[120].x=1219;ans[120].y=2725;ans[120].z=-2804;
ans[123].x=-16;ans[123].y=38;ans[123].z=-37;
ans[124].x=0;ans[124].y=5;ans[124].z=-1;
ans[125].x=5;ans[125].y=5000;ans[125].z=-5000;
ans[126].x=-419;ans[126].y=2217;ans[126].z=-2212;
ans[127].x=-3881;ans[127].y=4988;ans[127].z=-4034;
ans[128].x=-726;ans[128].y=3997;ans[128].z=-3989;
ans[129].x=-1238;ans[129].y=1801;ans[129].z=-1580;
ans[132].x=2;ans[132].y=5;ans[132].z=-1;
ans[133].x=167;ans[133].y=389;ans[133].z=-399;
ans[134].x=-1766;ans[134].y=3203;ans[134].z=-3013;
ans[135].x=-629;ans[135].y=1395;ans[135].z=-1351;
ans[136].x=816;ans[136].y=946;ans[136].z=-1116;
ans[137].x=-428;ans[137].y=801;ans[137].z=-758;
ans[138].x=-77;ans[138].y=103;ans[138].z=-86;
ans[141].x=104;ans[141].y=116;ans[141].z=-139;
ans[142].x=-3;ans[142].y=8;ans[142].z=-7;
ans[144].x=-2552;ans[144].y=3342;ans[144].z=-2746;
ans[145].x=-7;ans[145].y=10;ans[145].z=-8;
ans[146].x=-263;ans[146].y=376;ans[146].z=-327;
ans[147].x=1528;ans[147].y=2131;ans[147].z=-2366;
ans[150].x=260;ans[150].y=317;ans[150].z=-367;
ans[151].x=215;ans[151].y=447;ans[151].z=-463;
ans[152].x=486;ans[152].y=741;ans[152].z=-805;
ans[153].x=-695;ans[153].y=3744;ans[153].z=-3736;
ans[154].x=-516;ans[154].y=2145;ans[154].z=-2135;
ans[155].x=-1049;ans[155].y=3721;ans[155].z=-3693;
ans[159].x=383;ans[159].y=1526;ans[159].z=-1534;
ans[160].x=-1654;ans[160].y=3972;ans[160].z=-3874;
ans[161].x=-2476;ans[161].y=4980;ans[161].z=-4767;
ans[162].x=-1417;ans[162].y=4180;ans[162].z=-4125;
ans[163].x=-2943;ans[163].y=4033;ans[163].z=-3423;
ans[164].x=-59;ans[164].y=79;ans[164].z=-66;
ans[168].x=-574;ans[168].y=890;ans[168].z=-802;
ans[169].x=-1012;ans[169].y=1521;ans[169].z=-1354;
ans[170].x=-2149;ans[170].y=4047;ans[170].z=-3834;
ans[171].x=891;ans[171].y=1178;ans[171].z=-1328;
ans[174].x=-170;ans[174].y=349;ans[174].z=-335;
ans[177].x=-160;ans[177].y=1169;ans[177].z=-1168;
ans[178].x=-10;ans[178].y=15;ans[178].z=-13;
ans[179].x=1503;ans[179].y=2691;ans[179].z=-2839;
ans[181].x=974;ans[181].y=4861;ans[181].z=-4874;
ans[182].x=-29;ans[182].y=91;ans[182].z=-90;
ans[183].x=976;ans[183].y=4876;ans[183].z=-4889;
ans[186].x=5;ans[186].y=5;ans[186].z=-4;
ans[187].x=-1092;ans[187].y=2000;ans[187].z=-1885;
ans[188].x=318;ans[188].y=1635;ans[188].z=-1639;
ans[189].x=-1403;ans[189].y=1974;ans[189].z=-1702;
ans[190].x=-593;ans[190].y=4815;ans[190].z=-4812;
ans[191].x=-215;ans[191].y=399;ans[191].z=-377;
ans[192].x=16;ans[192].y=16;ans[192].z=-20;
ans[196].x=-579;ans[196].y=1112;ans[196].z=-1057;
ans[197].x=-1606;ans[197].y=3026;ans[197].z=-2867;
ans[198].x=-1347;ans[198].y=3809;ans[198].z=-3752;
ans[199].x=508;ans[199].y=2199;ans[199].z=-2208;
ans[200].x=-638;ans[200].y=2334;ans[200].z=-2318;
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
if(ans[n].x==inf) printf("impossible\n");
else printf("%d %d %d\n",ans[n].x,ans[n].y,ans[n].z);
}
} H.Yuuki and a problem（树状数组套主席树）
题意：
给出一个序列，支持两个操作：
- 操作1：将
的值改成
- 操作2：询问不能被
...
里面的数通过任意相加构成的最小正整数
题解：
操作2需要我们提取[l,r]范围内的值，这可以用主席树解决，同时需要带修，所以可以用树状数组套主席树完成。
确定是树套树后，考虑怎么维护操作2。
我们考虑一个节点，先看看能不能表示成1，如果这个节点代表的区间一个1都没有，那他的答案为1。
假设答案已经可以构成[1,x]了。
那么我们求出的所有数的和
，如果
,那么答案就是x+1。
否则将区间更新为,继续更新
这个过程可以直接暴力，最坏情况下当前区间里的数是，是一个斐波那契数列，在第27项就到到
了，所以最多跑
次
这个过程可以暴力跑，因为他，不到多少项就到了。
所以我们操作2就相当于是模拟这样一个过程。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n, m, len;
ll a[maxn];
ll sum[maxn * 80];
int ls[maxn * 80], rs[maxn * 80], rt[maxn * 80];
int tot;
inline int lowbit(int x) { return x & (-x); }
void update_SgT(int &rt, int l, int r, int pos, int val)
{
if (!rt)
rt = ++tot;
if (l == r)
{
sum[rt] += val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
update_SgT(ls[rt], l, mid, pos, val);
else
update_SgT(rs[rt], mid + 1, r, pos, val);
sum[rt] = sum[ls[rt]] + sum[rs[rt]];
}
void update_BIT(int pos, int x, int val)
{
for (int i = pos; i <= n; i += lowbit(i))
update_SgT(rt[i], 1, len, x, val);
}
int rt1[maxn], rt2[maxn], cnt1, cnt2;
void locate(int l, int r)
{
cnt1 = cnt2 = 0;
for (int i = l - 1; i; i -= lowbit(i))
rt1[++cnt1] = rt[i];
for (int i = r; i; i -= lowbit(i))
rt2[++cnt2] = rt[i];
}
ll ask(int l, int r, int k)
{
ll ans = 0;
if (r == k)
{
for (int i = 1; i <= cnt1; i++)
ans -= sum[rt1[i]];
for (int i = 1; i <= cnt2; i++)
ans += sum[rt2[i]];
return ans;
}
int mid = (l + r) >> 1;
if (k <= mid)
{
for (int i = 1; i <= cnt1; i++)
rt1[i] = ls[rt1[i]];
for (int i = 1; i <= cnt2; i++)
rt2[i] = ls[rt2[i]];
return ask(l, mid, k);
}
else
{
for (int i = 1; i <= cnt1; i++)
ans -= sum[ls[rt1[i]]];
for (int i = 1; i <= cnt2; i++)
ans += sum[ls[rt2[i]]];
for (int i = 1; i <= cnt1; i++)
rt1[i] = rs[rt1[i]];
for (int i = 1; i <= cnt2; i++)
rt2[i] = rs[rt2[i]];
return ans + ask(mid + 1, r, k);
}
}
int main()
{
scanf("%d%d", &n, &m);
len = maxn - 10;
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for (int i = 1; i <= n; i++)
update_BIT(i, a[i], a[i]);
for (int i = 1, op, x, y; i <= m; i++)
{
scanf("%d%d%d", &op, &x, &y);
if (op == 1)
{
update_BIT(x, a[x], -a[x]);
a[x] = y;
update_BIT(x, y, y);
}
else
{
ll now = 1;
ll sum = 0;
while (true)
{
locate(x, y);
int t = min(now, 200000ll);
ll tmp = ask(1, len, t);
if (tmp == sum)
{
printf("%lld\n", now);
break;
}
sum = tmp;
now = sum + 1;
}
}
}
return 0;
} M.Kill the tree（树重心）
题意：
给你一颗以1为根，规模为的树。让你求出以每个点为根的子树中，到子树中每个点距离和最小的点。
题解：
首先先做条件转化，到子树中每个点距离和最小，等价于重心，所以问题变成了求每棵子树的重心。
树重心的一些性质：
- 树的重心最多只有两个，且一定挨着
- 一棵的重心只会在根节点到各个子树重心的路径上
那么我们对于每棵树，每次都从它的各个子树重心往上找。设当前点心为，根节点为
，
是以
结点的为根节点的子树的结点个数。若
往上爬，
的所有子节点到
的距离会加一，其它点到
的距离会减一，根据题目给那么得到一个条件是
，满足这个条件
就可以向上爬，直到到达根节点或者条件不满足
因为可能存在两个重心，所以对于每棵子树每次只取深度较大者为重心，最后在对每个节点判断一下该点重心的父节点是否满足条件即可：因为重心为最优，所以只要判断重心的父节点是否同样为最优即可，
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
vector<int> g[maxn], ans[maxn];
int n, siz[maxn], f[maxn], son[maxn], deep[maxn];
int update(int rt, int x, int y)
{
while (deep[x] > deep[rt] && siz[rt] - siz[x] > siz[x])
x = f[x];
while (deep[y] > deep[rt] && siz[rt] - siz[y] > siz[y])
y = f[y];
if (deep[x] > deep[y])
son[rt] = x;
else
son[rt] = y;
}
void dfs(int u, int fa)
{
siz[u] = 1, son[u] = u;
f[u] = fa;
for (auto v : g[u])
{
if (v == fa)
continue;
deep[v] = deep[u] + 1;
dfs(v, u);
siz[u] += siz[v];
update(u, son[u], son[v]);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
deep[1] = 1;
dfs(1, 0);
for (int i = 1; i <= n; i++)
{
ans[i].push_back(son[i]);
if (f[son[i]] && siz[i] - siz[son[i]] == siz[son[i]])
ans[i].push_back(f[son[i]]);
sort(ans[i].begin(), ans[i].end());
for (int j = 0; j < ans[i].size(); j++)
printf("%d%s", ans[i][j], j == ans[i].size() - 1 ? "\n" : " ");
}
return 0;
} 
京公网安备 11010502036488号