codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1797.md (15573B)


      1 Source: https://codeforces.com/blog/entry/114890
      2 
      3 [1797A - Li Hua and Maze](/contest/1797/problem/A "Codeforces Round 864 (Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (rui_er)**
     10 
     11 ```
     12 //By: OIer rui_er
     13 #include <bits/stdc++.h>
     14 #define rep(x,y,z) for(int x=(y);x<=(z);x++)
     15 #define per(x,y,z) for(int x=(y);x>=(z);x--)
     16 #define debug(format...) fprintf(stderr, format)
     17 #define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
     18 using namespace std;
     19 typedef long long ll;
     20  
     21 #define y1 y114514
     22 int T, n, m, x1, y1, x2, y2;
     23 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
     24 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
     25 int f(int x, int y) {
     26 	if((x == 1 || x == n) && (y == 1 || y == m)) return 2;
     27 	if(x == 1 || x == n || y == 1 || y == m) return 3;
     28 	return 4;
     29 }
     30  
     31 int main() {
     32 	for(scanf("%d", &T);T;T--) {
     33 		scanf("%d%d%d%d%d%d", &n, &m, &x1, &y1, &x2, &y2);
     34 		printf("%d\n", min(f(x1, y1), f(x2, y2)));
     35 	}
     36 	return 0;
     37 }
     38 ```
     39 
     40 [1797B - Li Hua and Pattern](/contest/1797/problem/B "Codeforces Round 864 (Div. 2)")
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 **Solution (rui_er)**
     47 
     48 ```
     49 //By: OIer rui_er
     50 #include <bits/stdc++.h>
     51 #define rep(x,y,z) for(int x=(y);x<=(z);x++)
     52 #define per(x,y,z) for(int x=(y);x>=(z);x--)
     53 #define debug(format...) fprintf(stderr, format)
     54 #define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
     55 using namespace std;
     56 typedef long long ll;
     57 const int N = 1e3+5;
     58  
     59 int T, n, k, a[N][N];
     60 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
     61 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
     62  
     63 int main() {
     64 	for(scanf("%d", &T);T;T--) {
     65 		scanf("%d%d", &n, &k);
     66 		rep(i, 1, n) rep(j, 1, n) scanf("%d", &a[i][j]);
     67 		int diff = 0;
     68 		rep(i, 1, n) rep(j, 1, n) if(a[i][j] != a[n+1-i][n+1-j]) ++diff;
     69 		diff /= 2;
     70 		if(diff > k) puts("NO");
     71 		else {
     72 			k -= diff;
     73 			if(n & 1) puts("YES");
     74 			else if(k & 1) puts("NO");
     75 			else puts("YES");
     76 		}
     77 	}
     78 	return 0;
     79 }
     80 ```
     81 
     82 [1797C - Li Hua and Chess](/contest/1797/problem/C "Codeforces Round 864 (Div. 2)")
     83 
     84 **Tutorial**
     85 
     86 Tutorial is loading...
     87 
     88 **Solution (rui_er)**
     89 
     90 ```
     91 #include <bits/stdc++.h>
     92 using namespace std;
     93  
     94 int T, n, m;
     95  
     96 int ask(int x, int y) {
     97 	printf("? %d %d\n", x, y);
     98 	fflush(stdout);
     99 	scanf("%d", &x);
    100 	return x;
    101 }
    102  
    103 void give(int x, int y) {
    104 	printf("! %d %d\n", x, y);
    105 	fflush(stdout);
    106 }
    107  
    108 int main() {
    109 	for(scanf("%d", &T);T;T--) {
    110 		scanf("%d%d", &n, &m);
    111 		int T1 = ask(1, 1);
    112 		if(T1 >= n) {
    113 			int T2 = ask(1, T1+1);
    114 			give(T2+1, T1+1);
    115 		}
    116 		else if(T1 >= m) {
    117 			int T2 = ask(T1+1, 1);
    118 			give(T1+1, T2+1);
    119 		}
    120 		else {
    121 			int T2 = ask(T1+1, 1);
    122 			int T3 = ask(1, T1+1);
    123 			if(T2 == T1 && T3 == T1) give(T1+1, T1+1);
    124 			else if(T3 == T1) give(T1+1, T2+1);
    125 			else give(T3+1, T1+1);
    126 		}
    127 	}
    128 	return 0;
    129 }
    130 ```
    131 
    132 [1797D - Li Hua and Tree](/contest/1797/problem/D "Codeforces Round 864 (Div. 2)")
    133 
    134 **Tutorial**
    135 
    136 Tutorial is loading...
    137 
    138 **Solution (rui_er)**
    139 
    140 ```
    141 //By: Luogu@rui_er(122461)
    142 #include <bits/stdc++.h>
    143 #define rep(x,y,z) for(ll x=y;x<=z;x++)
    144 #define per(x,y,z) for(ll x=y;x>=z;x--)
    145 #define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
    146 #define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
    147 using namespace std;
    148 typedef long long ll;
    149 const ll N = 1e5+5; 
    150  
    151 ll n, m, a[N], sz[N], son[N], fa[N], sum[N];
    152 vector<ll> e[N];
    153 set<tuple<ll, ll> > sons[N]; 
    154 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
    155 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
    156 void dfs(ll u, ll f) {
    157 	sz[u] = 1;
    158 	sum[u] = a[u];
    159 	fa[u] = f;
    160 	for(auto v : e[u]) {
    161 		if(v == f) continue;
    162 		dfs(v, u);
    163 		sz[u] += sz[v];
    164 		sum[u] += sum[v];
    165 		sons[u].insert(make_tuple(-sz[v], v));
    166 		if(sz[v] > sz[son[u]] || sz[v] == sz[son[u]] && v < son[u]) son[u] = v;
    167 	}
    168 }
    169  
    170 int main() {
    171 	scanf("%lld%lld", &n, &m);
    172 	rep(i, 1, n) scanf("%lld", &a[i]);
    173 	rep(i, 1, n-1) {
    174 		ll u, v;
    175 		scanf("%lld%lld", &u, &v);
    176 		e[u].push_back(v);
    177 		e[v].push_back(u);
    178 	}
    179 	dfs(1, 0);
    180 	while(m --> 0) {
    181 		ll op, u;
    182 		scanf("%lld%lld", &op, &u);
    183 		if(op == 1) printf("%lld\n", sum[u]);
    184 		else {
    185 			ll v = son[u];
    186 			if(!v) continue;
    187 			ll p = fa[u];
    188 			sz[u] -= sz[v];
    189 			sum[u] -= sum[v];
    190 			sons[u].erase(make_tuple(-sz[v], v));
    191 			son[u] = sons[u].empty() ? 0 : get<1>(*sons[u].begin());
    192 			fa[u] = v;
    193 			sz[v] += sz[u];
    194 			sum[v] += sum[u];
    195 			sons[v].insert(make_tuple(-sz[u], u));
    196 			son[v] = get<1>(*sons[v].begin());
    197 			fa[v] = p;
    198 			sons[p].erase(make_tuple(-sz[v], u));
    199 			sons[p].insert(make_tuple(-sz[v], v));
    200 			son[p] = get<1>(*sons[p].begin());
    201 		}
    202 	}
    203 	return 0;
    204 }
    205 ```
    206 
    207 [1797E - Li Hua and Array](/contest/1797/problem/E "Codeforces Round 864 (Div. 2)")
    208 
    209 **Tutorial**
    210 
    211 Tutorial is loading...
    212 
    213 **Solution (rui_er)**
    214 
    215 ```
    216 //By: Luogu@rui_er(122461)
    217 #include <bits/stdc++.h>
    218 #define rep(x,y,z) for(int x=y;x<=z;x++)
    219 #define per(x,y,z) for(int x=y;x>=z;x--)
    220 #define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
    221 #define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
    222 using namespace std;
    223 typedef long long ll;
    224 const int N = 1e5 + 5, P = 4e5 + 5, K = 5e6 + 5, W = 5e6; 
    225  
    226 int n, m, a[N], tab[K], phi[K], p[P], pcnt, dis[K], fa[K][6];
    227 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
    228 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
    229 void sieve(int lim) {
    230 	phi[1] = 1;
    231 	rep(i, 2, lim) {
    232 		if(!tab[i]) {
    233 			p[++pcnt] = i;
    234 			phi[i] = i - 1;
    235 		}
    236 		for(int j=1;j<=pcnt&&1LL*i*p[j]<=lim;j++) {
    237 			tab[i*p[j]] = 1;
    238 			if(i % p[j]) phi[i*p[j]] = phi[i] * phi[p[j]];
    239 			else {
    240 				phi[i*p[j]] = phi[i] * p[j];
    241 				break;
    242 			}
    243 		}
    244 	}
    245 }
    246 void initTree(int lim) {
    247 	dis[1] = 1;
    248 	rep(j, 0, 5) fa[1][j] = 1;
    249 	rep(i, 2, lim) {
    250 		dis[i] = dis[phi[i]] + 1;
    251 		fa[i][0] = phi[i];
    252 		rep(j, 1, 5) fa[i][j] = fa[fa[i][j-1]][j-1];
    253 	}
    254 }
    255 int LCA(int u, int v) {
    256 	if(dis[u] < dis[v]) swap(u, v);
    257 	per(i, 5, 0) if(dis[fa[u][i]] >= dis[v]) u = fa[u][i];
    258 	if(u == v) return u;
    259 	per(i, 5, 0) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    260 	return fa[u][0];
    261 }
    262 struct Node {
    263 	int lca, ans, mndis, allrt;
    264 };
    265 struct SegTree {
    266 	Node t[N<<2];
    267 	#define lc(u) (u<<1)
    268 	#define rc(u) (u<<1|1)
    269 	void pushup(int u, int l, int r) {
    270 		int mid = (l + r) >> 1;
    271 		t[u].lca = LCA(t[lc(u)].lca, t[rc(u)].lca);
    272 		t[u].ans = t[lc(u)].ans + t[rc(u)].ans
    273 				 + (mid - l + 1) * (dis[t[lc(u)].lca] - dis[t[u].lca])
    274 				 + (r - mid) * (dis[t[rc(u)].lca] - dis[t[u].lca]);
    275 		t[u].mndis = min(t[lc(u)].mndis, t[rc(u)].mndis);
    276 		t[u].allrt = t[lc(u)].allrt && t[rc(u)].allrt;
    277 	}
    278 	void build(int u, int l, int r) {
    279 		if(l == r) {
    280 			t[u].lca = a[l];
    281 			t[u].ans = 0;
    282 			t[u].mndis = dis[a[l]];
    283 			t[u].allrt = a[l] == 1;
    284 			return;
    285 		}
    286 		int mid = (l + r) >> 1;
    287 		build(lc(u), l, mid);
    288 		build(rc(u), mid+1, r);
    289 		pushup(u, l, r);
    290 	}
    291 	void modify(int u, int l, int r, int ql, int qr) {
    292 		if(t[u].allrt) return;
    293 		if(l == r) {
    294 			t[u].lca = fa[t[u].lca][0];
    295 			--t[u].mndis;
    296 			t[u].allrt = t[u].lca == 1;
    297 			return;
    298 		}
    299 		int mid = (l + r) >> 1;
    300 		if(ql <= mid) modify(lc(u), l, mid, ql, qr);
    301 		if(qr > mid) modify(rc(u), mid+1, r, ql, qr);
    302 		pushup(u, l, r);
    303 	}
    304 	int queryLCA(int u, int l, int r, int ql, int qr) {
    305 		if(ql <= l && r <= qr) return t[u].lca;
    306 		int mid = (l + r) >> 1;
    307 		if(qr <= mid) return queryLCA(lc(u), l, mid, ql, qr);
    308 		if(ql > mid) return queryLCA(rc(u), mid+1, r, ql, qr);
    309 		int ans = queryLCA(lc(u), l, mid, ql, qr);
    310 		if(ans == 1) return 1;
    311 		return LCA(ans, queryLCA(rc(u), mid+1, r, ql, qr));
    312 	}
    313 	int queryAns(int u, int l, int r, int ql, int qr, int lca) {
    314 		if(ql <= l && r <= qr) {
    315 			return t[u].ans + (r - l + 1) * (dis[t[u].lca] - dis[lca]);
    316 		}
    317 		int mid = (l + r) >> 1, ans = 0;
    318 		if(ql <= mid) ans += queryAns(lc(u), l, mid, ql, qr, lca);
    319 		if(qr > mid) ans += queryAns(rc(u), mid+1, r, ql, qr, lca);
    320 		return ans;
    321 	}
    322 	#undef lc
    323 	#undef rc
    324 }sgt;
    325  
    326 int main() {
    327 	sieve(W);
    328 	initTree(W);
    329 	scanf("%d%d", &n, &m);
    330 	rep(i, 1, n) scanf("%d", &a[i]);
    331 	sgt.build(1, 1, n);
    332 	while(m --> 0) {
    333 		int op, l, r;
    334 		scanf("%d%d%d", &op, &l, &r);
    335 		if(op == 1) sgt.modify(1, 1, n, l, r);
    336 		else {
    337 			int lca = sgt.queryLCA(1, 1, n, l, r);
    338 			printf("%d\n", sgt.queryAns(1, 1, n, l, r, lca));
    339 		}
    340 	}
    341 	return 0;
    342 }
    343 ```
    344 
    345 [1797F - Li Hua and Path](/contest/1797/problem/F "Codeforces Round 864 (Div. 2)")
    346 
    347 **Tutorial**
    348 
    349 Tutorial is loading...
    350 
    351 **Solution (Celtic, centroid decomposition)**
    352 
    353 ```
    354 // Celtic
    355 #include<bits/stdc++.h> 
    356 #define N 501001
    357 #define MAX 2005
    358 using namespace std;
    359 typedef long long ll;
    360 typedef long double db;
    361 const ll inf=1e18,mod=998244353,inv3=(mod+1)/3;
    362 inline void read(ll &ret)
    363 {
    364 	ret=0;char c=getchar();bool pd=false;
    365 	while(!isdigit(c)){pd|=c=='-';c=getchar();}
    366 	while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();}
    367 	ret=pd?-ret:ret;
    368 	return;
    369 }
    370 ll n,m,x,y,siz[N],son[N],minn=inf,num=0,f[N],sum,root;
    371 vector<ll>v[N];
    372 bool vis[N];
    373 inline void find(ll ver,ll fa)
    374 {
    375 	siz[ver]=1;
    376 	ll maxn=0;
    377 	for(int i=0;i<v[ver].size();i++)
    378 	{
    379 		ll to=v[ver][i];
    380 		if(to==fa||vis[to])
    381 			continue;
    382 		find(to,ver);
    383 		siz[ver]+=siz[to];
    384 		maxn=max(maxn,siz[to]);
    385 	}
    386 	maxn=max(maxn,num-siz[ver]);
    387 	if(maxn<minn)
    388 	{
    389 		minn=maxn;
    390 		root=ver;
    391 	}
    392 	return;
    393 }
    394 ll valmx[N],valmn[N],sz[N],now,fat[N];
    395 struct node
    396 {
    397 	ll x,y,ver;
    398 }a[N];
    399 inline bool cmp1(node a,node b)
    400 {
    401 	return a.x<b.x;
    402 }
    403 inline bool cmp2(node a,node b)
    404 {
    405 	return a.y<b.y;
    406 }
    407 ll cnt;
    408 vector<ll>g[N];
    409 inline void dfs(ll ver,ll fa,ll d)
    410 {
    411 	valmx[ver]=max(valmx[fa],ver);
    412 	valmn[ver]=min(valmn[fa],ver);
    413 	if(ver!=now)
    414 	{
    415 		if(valmx[ver]==ver||valmx[ver]==now)
    416 			sum++;
    417 		if(valmn[ver]==ver||valmn[ver]==now)
    418 			sum++;
    419 		if(valmx[ver]==ver&&valmn[ver]==now)
    420 			sum-=2;
    421 		if(valmx[ver]==now&&valmn[ver]==ver)
    422 			sum-=2;
    423 		if(valmn[ver]==ver)
    424 			f[now]++;
    425 		if(valmn[ver]==now)
    426 			f[ver]++;
    427 		g[d].push_back(ver);
    428 		a[++cnt]=node{valmx[ver],valmn[ver],ver};
    429 	}
    430 	sz[ver]=1;
    431 	fat[ver]=d;
    432 //	cout<<"dfs"<<ver<<" "<<fa<<" "<<d<<endl;
    433 	for(int i=0;i<v[ver].size();i++)
    434 	{
    435 		ll to=v[ver][i];
    436 		if(to==fa||vis[to])
    437 			continue;
    438 		if(ver==now)
    439 			dfs(to,ver,to);
    440 		else
    441 			dfs(to,ver,d);
    442 		sz[ver]+=sz[to];
    443 	}
    444 	return;
    445 }
    446 ll tree[N];
    447 inline void update(ll pos,ll num)
    448 {
    449 	pos++;
    450 	while(pos<N)
    451 	{
    452 		tree[pos]+=num;
    453 		pos+=pos&-pos;
    454 	}
    455 	return;
    456 }
    457 inline ll query(ll pos)
    458 {
    459 	pos++;
    460 	ll ret=0;
    461 	while(pos)
    462 	{
    463 		ret+=tree[pos];
    464 		pos-=pos&-pos; 
    465 	}
    466 	return ret;
    467 }
    468 inline void calc()
    469 {
    470 	sort(a+1,a+cnt+1,cmp1);
    471 	for(int i=1;i<=cnt;i++)
    472 	{
    473 		ll j=i;
    474 		for(;j<=cnt&&a[j].x==a[i].x;j++);
    475 		j--;
    476 		for(int k=i;k<=j;k++)
    477 		{
    478 			if(a[k].x==a[k].ver)
    479 				sum+=i-1,sum-=2*query(a[k].y)/*,cout<<"del "<<a[k].ver<<" "<<i-1<<" "<<query(a[k].y)<<endl*/;
    480 		}
    481 		for(int k=i;k<=j;k++)
    482 		{
    483 			if(a[k].y==a[k].ver)
    484 				update(a[k].y,1);
    485 		}
    486 		i=j;
    487 	}
    488 	for(int i=1;i<=cnt;i++)
    489 	{
    490 		ll j=i;
    491 		for(;j<=cnt&&a[j].x==a[i].x;j++);
    492 		j--;
    493 		for(int k=i;k<=j;k++)
    494 		{
    495 			if(a[k].y==a[k].ver)
    496 				update(a[k].y,-1);
    497 		}
    498 		i=j;
    499 	}
    500 	sort(a+1,a+cnt+1,cmp2);
    501 	for(int i=cnt;i;i--)
    502 	{
    503 		ll j=i;
    504 		for(;j&&a[j].y==a[i].y;j--);
    505 		j++;
    506 		for(int k=j;k<=i;k++)
    507 		{
    508 			if(a[k].y==a[k].ver)
    509 				sum+=cnt-i;
    510 		}
    511 		i=j;
    512 	}
    513 	ll tmp=0;
    514 	for(int i=1;i<=cnt;i++)
    515 	{
    516 		ll j=i;
    517 		for(;j<=cnt&&a[j].y==a[i].y;j++);
    518 		j--;
    519 		for(int k=i;k<=j;k++)
    520 			f[a[k].ver]+=tmp;
    521 		for(int k=i;k<=j;k++)
    522 			if(a[k].ver==a[k].y)
    523 				tmp++;
    524 		i=j;
    525 	}
    526 	return;
    527 }
    528 inline void decalc()
    529 {
    530 	sort(a+1,a+cnt+1,cmp1);
    531 	for(int i=1;i<=cnt;i++)
    532 	{
    533 		ll j=i;
    534 		for(;j<=cnt&&a[j].x==a[i].x;j++);
    535 		j--;
    536 		for(int k=i;k<=j;k++)
    537 		{
    538 			if(a[k].x==a[k].ver)
    539 				sum-=i-1,sum+=2*query(a[k].y)/*,cout<<"back"<<a[k].ver<<" "<<i-1<<" "<<query(a[k].y)<<endl*/;
    540 		}
    541 		for(int k=i;k<=j;k++)
    542 		{
    543 			if(a[k].y==a[k].ver)
    544 				update(a[k].y,1);
    545 		}
    546 		i=j;
    547 	}
    548 	for(int i=1;i<=cnt;i++)
    549 	{
    550 		ll j=i;
    551 		for(;j<=cnt&&a[j].x==a[i].x;j++);
    552 		j--;
    553 		for(int k=i;k<=j;k++)
    554 		{
    555 			if(a[k].y==a[k].ver)
    556 				update(a[k].y,-1);
    557 		}
    558 		i=j;
    559 	}
    560 	sort(a+1,a+cnt+1,cmp2);
    561 	for(int i=cnt;i;i--)
    562 	{
    563 		ll j=i;
    564 		for(;j&&a[j].y==a[i].y;j--);
    565 		j++;
    566 		for(int k=j;k<=i;k++)
    567 		{
    568 			if(a[k].y==a[k].ver)
    569 				sum-=cnt-i;
    570 		}
    571 		i=j;
    572 	}
    573 	ll tmp=0;
    574 	for(int i=1;i<=cnt;i++)
    575 	{
    576 		ll j=i;
    577 		for(;j<=cnt&&a[j].y==a[i].y;j++);
    578 		j--;
    579 		for(int k=i;k<=j;k++)
    580 			f[a[k].ver]-=tmp;
    581 		for(int k=i;k<=j;k++)
    582 			if(a[k].ver==a[k].y)
    583 				tmp++;
    584 		i=j;
    585 	}
    586 	return;
    587 }
    588 inline void divide(ll ver)
    589 {
    590 	vis[ver]=true;
    591 	now=ver;
    592 	cnt=0;
    593 	valmn[0]=inf;
    594 	dfs(ver,0,0);
    595 //	cout<<"??"<<ver<<" "<<sum<<endl;
    596 /*	cout<<ver<<endl;
    597 	for(int i=1;i<=cnt;i++)
    598 		cout<<a[i].x<<" "<<a[i].y<<endl;*/
    599 	calc();
    600 //	cout<<ver<<" "<<cnt<<endl;
    601 	for(int i=0;i<v[ver].size();i++)
    602 	{
    603 		ll to=v[ver][i];
    604 		if(vis[to])
    605 			continue;
    606 		cnt=0;
    607 		for(auto x:g[to])
    608 			a[++cnt]=node{valmx[x],valmn[x],x}/*,cout<<ver<<" "<<to<<" "<<x<<endl*/;
    609 		g[to].clear();
    610 	//	cout<<ver<<" "<<to<<" "<<cnt<<endl;
    611 		decalc();
    612 	}
    613 //	cout<<"result::"<<ver<<" "<<sum<<endl;
    614 	for(int i=0;i<v[ver].size();i++)
    615 	{
    616 		ll to=v[ver][i];
    617 		if(vis[to])
    618 			continue;
    619 		num=siz[to];
    620 		minn=inf;
    621 		find(to,ver);
    622 	//	cout<<ver<<" "<<to<<" "<<root<<endl;
    623 		divide(root);
    624 	}
    625 	return;
    626 }
    627 signed main()
    628 {
    629 	read(n);
    630 	for(int i=1;i<n;i++)
    631 	{
    632 		read(x);
    633 		read(y);
    634 		v[x].push_back(y);
    635 		v[y].push_back(x);
    636 	}
    637 	num=n;
    638 	find(1,0);
    639 	divide(root);
    640 	printf("%lld\n",sum);
    641 /*	for(int i=1;i<=n;i++)
    642 		cout<<f[i]<<" ";
    643 	cout<<endl;*/
    644 	read(m);
    645 	for(int i=1;i<=m;i++)
    646 	{
    647 		ll x;
    648 		read(x);
    649 		n++;
    650 		f[n]=f[x]+1;
    651 		sum+=(n-1)-f[n];
    652 		printf("%lld\n",sum);
    653 	}
    654 	exit(0);
    655 }
    656 ```
    657 
    658 **Solution (rui_er, reconstruction trees)**
    659 
    660 ```
    661 //By: OIer rui_er
    662 #include <bits/stdc++.h>
    663 #define rep(x,y,z) for(ll x=(y);x<=(z);x++)
    664 #define per(x,y,z) for(ll x=(y);x>=(z);x--)
    665 #define debug(format...) fprintf(stderr, format)
    666 #define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
    667 using namespace std;
    668 typedef long long ll;
    669 const ll N = 4e5+5;
    670  
    671 ll n, m, k, faMx[N], faMn[N], disMx[N], disMn[N], dfn[N], sz[N], tms;
    672 ll A, B, C, ans;
    673 vector<ll> eMx[N], eMn[N], reMx[N], reMn[N];
    674 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
    675 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
    676 struct Dsu {
    677 	ll fa[N];
    678 	void init(ll x) {rep(i, 1, x) fa[i] = i;}
    679 	ll find(ll x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
    680 	bool merge(ll x, ll y) {
    681 		ll u = find(x), v = find(y);
    682 		if(u == v) return 0;
    683 		fa[u] = v;
    684 		return 1;
    685 	}
    686 }dsu;
    687 struct BIT {
    688 	ll c[N], sz;
    689 	void init(ll x) {sz = x; rep(i, 1, x) c[i] = 0;}
    690 	ll lowbit(ll x) {return x & (-x);}
    691 	void add(ll x, ll k) {for(; x <= sz; x += lowbit(x)) c[x] += k;}
    692 	ll ask(ll x) {ll k = 0; for(; x; x -= lowbit(x)) k += c[x]; return k;}
    693 	ll Ask(ll x, ll y) {return ask(y) - ask(x - 1);}
    694 }bit;
    695 void dfs1(ll u) {
    696 	dfn[u] = ++tms;
    697 	sz[u] = 1;
    698 	disMx[u] = disMx[faMx[u]] + 1;
    699 	B += disMx[u] - 1;
    700 	for(ll v : reMx[u]) {
    701 		dfs1(v);
    702 		sz[u] += sz[v];
    703 	}
    704 }
    705 void dfs2(ll u) {
    706 	disMn[u] = disMn[faMn[u]] + 1;
    707 	A += disMn[u] - 1;
    708 	C += bit.Ask(dfn[u], dfn[u] + sz[u] - 1);
    709 	bit.add(dfn[u], 1);
    710 	for(ll v : reMn[u]) dfs2(v);
    711 	bit.add(dfn[u], -1);
    712 }
    713  
    714 int main() {
    715 	scanf("%lld", &n);
    716 	rep(i, 1, n-1) {
    717 		ll u, v;
    718 		scanf("%lld%lld", &u, &v);
    719 		if(u < v) swap(u, v);
    720 		eMx[u].push_back(v);
    721 		eMn[v].push_back(u);
    722 	}
    723 	dsu.init(n);
    724 	rep(i, 1, n) {
    725 		for(ll j : eMx[i]) {
    726 			j = dsu.find(j);
    727 			dsu.merge(j, i);
    728 			faMx[j] = i;
    729 			reMx[i].push_back(j);
    730 		}
    731 	}
    732 	dsu.init(n);
    733 	per(i, n, 1) {
    734 		for(ll j : eMn[i]) {
    735 			j = dsu.find(j);
    736 			dsu.merge(j, i);
    737 			faMn[j] = i;
    738 			reMn[i].push_back(j);
    739 		}
    740 	}
    741 	bit.init(n);
    742 	dfs1(n);
    743 	dfs2(1);
    744 	ans = A + B - 2 * C;
    745 	// printf("%lld + %lld - 2 * %lld = %lld\n", A, B, C, ans);
    746 	printf("%lld\n", ans);
    747 	for(scanf("%lld", &m); m; m--) {
    748 		scanf("%lld", &k);
    749 		disMn[++n] = disMn[k] + 1;
    750 		ans += n - disMn[n];
    751 		printf("%lld\n", ans);
    752 	}
    753 	return 0;
    754 }
    755 ```