codeforces-scrape

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

1336.md (16684B)


      1 Source: https://codeforces.com/blog/entry/76099
      2 
      3 [1337A - Ichihime and Triangle](/contest/1337/problem/A "Codeforces Round 635 (Div. 2)")
      4 
      5 Idea: [Sulfox](/profile/Sulfox "International Master Sulfox")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution by Sooke**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 using namespace std;
     16 
     17 int t, a, b, c, d;
     18 
     19 int main() {
     20     for (cin >> t; t; t--) {
     21         cin >> a >> b >> c >> d;
     22         cout << b << " " << c << " " << c << endl;
     23     }
     24     return 0;
     25 }
     26 ```
     27 
     28 [1337B - Kana and Dragon Quest game](/contest/1337/problem/B "Codeforces Round 635 (Div. 2)")
     29 
     30 Idea: [EternalAlexander](/profile/EternalAlexander "Master EternalAlexander")
     31 
     32 **Tutorial**
     33 
     34 Tutorial is loading...
     35 
     36 **Solution by EternalAlexander**
     37 
     38 ```
     39 #include <bits/stdc++.h>
     40 int x,n,m,t;
     41 void solve(){
     42 	scanf("%d%d%d",&x,&n,&m);
     43 	while (x>0&&n&&x/2+10<x){n--;x=x/2+10;}
     44 	if (x<=m*10)printf("YES\n");
     45 	else printf("NO\n"); 
     46 }
     47 int main(){
     48 	scanf("%d",&t);
     49 	while(t--)solve();
     50 	return 0;
     51 }
     52 ```
     53 
     54 [1336A - Linova and Kingdom](/contest/1336/problem/A "Codeforces Round 635 (Div. 1)")
     55 
     56 Idea: [EternalAlexander](/profile/EternalAlexander "Master EternalAlexander")
     57 
     58 **Tutorial**
     59 
     60 Tutorial is loading...
     61 
     62 **Solution by EternalAlexander**
     63 
     64 ```
     65 #include <bits/stdc++.h>
     66 #define maxn 200005
     67 std::vector<int>conj[maxn];
     68 int n,k,u,v,depth[maxn]={0},size[maxn]={0},det[maxn];
     69 long long ans=0;
     70 int cmp(int a,int b){return a>b;}
     71 int dfs(int u,int f){depth[u]=depth[f]+1;size[u]=1;
     72 	for (int i=0;i<conj[u].size();++i){
     73 		if ((v=conj[u][i])==f)continue;
     74 		size[u]+=dfs(v,u);
     75 	}det[u]=size[u]-depth[u];return size[u];
     76 }
     77 int main(){
     78 	scanf("%d%d",&n,&k);
     79 	for (int i=1;i<n;++i){
     80 		scanf("%d%d",&u,&v);conj[u].push_back(v);conj[v].push_back(u);
     81 	}dfs(1,0);
     82 	std::nth_element(det+1,det+n-k,det+n+1,cmp);
     83 	for (int i=1;i<=n-k;++i)ans+=det[i];std::cout<<ans;
     84 	return 0;
     85 }
     86 ```
     87 
     88 [1336B - Xenia and Colorful Gems](/contest/1336/problem/B "Codeforces Round 635 (Div. 1)")
     89 
     90 Idea: [ustze](/profile/ustze "Master ustze") & [isaf27](/profile/isaf27 "International Grandmaster isaf27")
     91 
     92 **Tutorial**
     93 
     94 Tutorial is loading...
     95 
     96 **Solution by Sooke**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100 using namespace std;
    101 
    102 int t, nr, ng, nb;
    103 long long ans;
    104 
    105 long long sq(int x) { return 1ll * x * x; }
    106 
    107 void solve(vector<int> a, vector<int> b, vector<int> c) {
    108     for (auto x : a) {
    109         auto y = lower_bound(b.begin(), b.end(), x);
    110         auto z = upper_bound(c.begin(), c.end(), x);
    111         if (y == b.end() || z == c.begin()) { continue; }
    112         z--; ans = min(ans, sq(x - *y) + sq(*y - *z) + sq(*z - x));
    113     }
    114 }
    115 
    116 int main() {
    117     for (cin >> t; t; t--) {
    118         cin >> nr >> ng >> nb;
    119         vector<int> r(nr), g(ng), b(nb);
    120         for (int i = 0; i < nr; i++) { cin >> r[i]; }
    121         for (int i = 0; i < ng; i++) { cin >> g[i]; }
    122         for (int i = 0; i < nb; i++) { cin >> b[i]; }
    123         sort(r.begin(), r.end());
    124         sort(g.begin(), g.end());
    125         sort(b.begin(), b.end());
    126         ans = 9e18;
    127         solve(r, g, b); solve(r, b, g);
    128         solve(g, b, r); solve(g, r, b);
    129         solve(b, r, g); solve(b, g, r);
    130         cout << ans << endl;
    131     }
    132     return 0;
    133 }
    134 ```
    135 
    136 [1336C - Kaavi and Magic Spell](/contest/1336/problem/C "Codeforces Round 635 (Div. 1)")
    137 
    138 Idea: [EternalAlexander](/profile/EternalAlexander "Master EternalAlexander")
    139 
    140 **Tutorial**
    141 
    142 Tutorial is loading...
    143 
    144 **Solution by ouuan**
    145 
    146 ```
    147 #include <iostream>
    148 #include <string>
    149 #include <vector>
    150 
    151 using namespace std;
    152 
    153 const int mod = 998244353;
    154 
    155 int main()
    156 {
    157 	string s, t;
    158 	
    159 	cin >> s >> t;
    160 	int n = s.size();
    161 	int m = t.size();
    162 	
    163 	vector<vector<int> > f(n + 1, vector<int>(m + 1));
    164 	
    165 	f[n][0] = 1;
    166 	
    167 	for (int i = n - 1; i >= 1; --i)
    168 	{
    169 		for (int j = 0; j <= m; ++j)
    170 		{
    171 			if (j == 0)
    172 			{
    173 				if (i >= m) f[i][0] = n - i + 1;
    174 				else if (s[i] == t[i]) f[i][0] = f[i + 1][0];
    175 			}
    176 			else if (j == m)
    177 			{
    178 				f[i][m] = 2 * f[i + 1][m] % mod;
    179 				if (s[i] == t[m - 1]) f[i][m] = (f[i][m] + f[i + 1][m - 1]) % mod;
    180 			}
    181 			else
    182 			{
    183 				if (i + j >= m || s[i] == t[i + j]) f[i][j] = f[i + 1][j];
    184 				if (s[i] == t[j - 1]) f[i][j] = (f[i][j] + f[i + 1][j - 1]) % mod;
    185 			}
    186 		}
    187 	}
    188 	
    189 	int ans = f[1][m];
    190 	for (int i = 0; i < m; ++i) if (t[i] == s[0]) ans = (ans + f[1][i]) % mod;
    191 	ans = ans * 2 % mod;
    192 	
    193 	cout << ans;
    194 	
    195 	return 0;
    196 }
    197 ```
    198 
    199 [1336D - Yui and Mahjong Set](/contest/1336/problem/D "Codeforces Round 635 (Div. 1)")
    200 
    201 Idea: [Sulfox](/profile/Sulfox "International Master Sulfox")
    202 
    203 **Tutorial**
    204 
    205 Tutorial is loading...
    206 
    207 [PinkRabbitAFO](/profile/PinkRabbitAFO "International Grandmaster PinkRabbitAFO") gives another solution which inserts tiles with value $1$, $2$, $\ldots$, $n-1$, $1$ in order. See more details [here](https://codeforces.com/blog/entry/76092).
    208 
    209 **Solution by Sooke**
    210 
    211 ```
    212 #include <bits/stdc++.h>
    213 using namespace std;
    214 
    215 int n, s1, s2, t1, t2, d1[105], d2[105], a[105];
    216 
    217 int main() {
    218     cin >> n >> s1 >> s2;
    219     for (int i = n - 1; i >= 0; i--) {
    220         cout << "+ " << (i > 2 ? i : i % 2 + 1) << endl;
    221         t1 = s1; t2 = s2; cin >> s1 >> s2;
    222         d1[i] = s1 - t1; d2[i] = s2 - t2;
    223     }
    224     a[1] = sqrt(d1[0] * 2);
    225     a[3] = d2[0] - d2[2] - 1;
    226     a[2] = d2[2] / (a[3] + 1);
    227     a[4] = d2[1] / (a[3] + 1) - a[1] - 2;
    228     for (int i = 5; i <= n; i++) {
    229         a[i] = (d2[i - 2] - a[i - 4] * a[i - 3]) / (a[i - 1] + 1) - a[i - 3] - 1;
    230     }
    231     cout << "!"; a[n]++;
    232     for (int i = 1; i <= n; i++) { cout << " " << a[i]; }
    233     cout << endl;
    234     return 0;
    235 }
    236 ```
    237 
    238 **Solution by PinkRabbit**
    239 
    240 ```
    241 #include <cstdio>
    242 
    243 const int MN = 105;
    244 
    245 int N, lstv1, lstv2, v1, v2;
    246 int dv1[MN], dv2[MN], Tag[MN], Ans[MN];
    247 
    248 int main() {
    249 	scanf("%d", &N);
    250 	scanf("%d%d", &lstv1, &lstv2);
    251 	for (int i = 1; i < N; ++i) {
    252 		printf("+ %d\n", i), fflush(stdout);
    253 		scanf("%d%d", &v1, &v2);
    254 		dv1[i] = v1 - lstv1, dv2[i] = v2 - lstv2;
    255 		if (dv1[i] > 0)
    256 			for (int x = 2; x <= N; ++x)
    257 				if (x * (x - 1) / 2 == dv1[i]) {
    258 					Tag[i] = x; break;
    259 				}
    260 		lstv1 = v1, lstv2 = v2;
    261 	}
    262 	printf("+ 1\n"), fflush(stdout);
    263 	scanf("%d%d", &v1, &v2);
    264 	int ndv1 = v1 - lstv1, ndv2 = v2 - lstv2;
    265 	for (int x = 0; x <= N; ++x)
    266 		if (x * (x + 1) / 2 == ndv1) {
    267 			Ans[1] = x; break;
    268 		}
    269 	int delta = ndv2 - dv2[1] - 1; // delta = a[2] + a[3]
    270 	if (Tag[2] >= 2) Ans[2] = Tag[2], Ans[3] = delta - Ans[2];
    271 	else if (Tag[3] >= 2) Ans[3] = Tag[3], Ans[2] = delta - Ans[3];
    272 	else if (delta == 0) Ans[3] = Ans[2] = 0;
    273 	else if (delta == 2) Ans[3] = Ans[2] = 1;
    274 	else if (dv2[2] > 0) Ans[2] = 0, Ans[3] = 1;
    275 	else Ans[2] = 1, Ans[3] = 0;
    276 	for (int i = 3; i <= N - 2; ++i) {
    277 		if (Tag[i + 1] >= 2) {
    278 			Ans[i + 1] = Tag[i + 1];
    279 			continue;
    280 		}
    281 		if ((Ans[i - 2] + 1) * (Ans[i - 1] + 1) == dv2[i]) Ans[i + 1] = 0;
    282 		else Ans[i + 1] = 1;
    283 	}
    284 	Ans[N] = (dv2[N - 1] - (Ans[N - 3] + 1) * (Ans[N - 2] + 1)) / (Ans[N - 2] + 1);
    285 	printf("!");
    286 	for (int i = 1; i <= N; ++i) printf(" %d", Ans[i]);
    287 	puts(""), fflush(stdout);
    288 	return 0;
    289 }
    290 ```
    291 
    292 [1336E1 - Chiori and Doll Picking (easy version)](/contest/1336/problem/E1 "Codeforces Round 635 (Div. 1)") and [1336E2 - Chiori and Doll Picking (hard version)](/contest/1336/problem/E2 "Codeforces Round 635 (Div. 1)")
    293 
    294 Idea: [Sulfox](/profile/Sulfox "International Master Sulfox")
    295 
    296 **Tutorial**
    297 
    298 Tutorial is loading...
    299 
    300 **Solution by Sooke**
    301 
    302 ```
    303 #include <bits/stdc++.h>
    304 using namespace std;
    305 
    306 const int mod = 998244353, inv2 = 499122177;
    307 const int M = 64;
    308 
    309 int n, m, k, p[M], c[M][M];
    310 long long a[M], b[M], f[M];
    311 
    312 void dfs(int i, long long x) {
    313     if (i == k) { p[__builtin_popcountll(x)]++; return; }
    314     dfs(i + 1, x); dfs(i + 1, x ^ a[i]);
    315 }
    316 
    317 int main() {
    318     cin >> n >> m;
    319     for (int i = 0; i < n; i++) {
    320         long long x; cin >> x;
    321         for (int j = m; j >= 0; j--) {
    322             if (x >> j & 1) {
    323                 if (!f[j]) { f[j] = x; break; }
    324                 x ^= f[j];
    325             }
    326         }
    327     }
    328     for (int i = 0; i < m; i++) {
    329         if (f[i]) {
    330             for (int j = 0; j < i; j++) {
    331                 if (f[i] >> j & 1) { f[i] ^= f[j]; }
    332             }
    333             for (int j = 0; j < m; j++) {
    334                 if (!f[j]) { a[k] = a[k] * 2 + (f[i] >> j & 1); }
    335             }
    336             a[k] |= 1ll << m - 1 - k; k++;
    337         }
    338     }
    339     if (k <= 26) {
    340         dfs(0, 0);
    341         for (int i = 0; i <= m; i++) {
    342             int ans = p[i];
    343             for (int j = 0; j < n - k; j++) { ans = ans * 2 % mod; }
    344             cout << ans << " ";
    345         }
    346     } else {
    347         k = m - k; swap(a, b);
    348         for (int i = 0; i < k; i++) {
    349             for (int j = 0; j < m - k; j++) {
    350                 if (b[j] >> i & 1) { a[i] |= 1ll << j; }
    351             }
    352             a[i] |= 1ll << m - 1 - i;
    353         }
    354         dfs(0, 0);
    355         for (int i = 0; i <= m; i++) {
    356             c[i][0] = 1;
    357             for (int j = 1; j <= i; j++) { c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; }
    358         }
    359         for (int i = 0; i <= m; i++) {
    360             int ans = 0;
    361             for (int j = 0; j <= m; j++) {
    362                 int coef = 0;
    363                 for (int k = 0; k <= i; k++) {
    364                     coef = (coef + (k & 1 ? -1ll : 1ll) * c[j][k] * c[m - j][i - k] % mod + mod) % mod;
    365                 }
    366                 ans = (ans + 1ll * coef * p[j]) % mod;
    367             }
    368             for (int j = 0; j < k; j++) { ans = 1ll * ans * inv2 % mod; }
    369             for (int j = 0; j < n - m + k; j++) { ans = ans * 2 % mod; }
    370             cout << ans << " ";
    371         }
    372     }
    373     return 0;
    374 }
    375 ```
    376 
    377 **Bonus**
    378 
    379 Solve the same problem with $m \le 63$.
    380 
    381 [1336F - Journey](/contest/1336/problem/F "Codeforces Round 635 (Div. 1)")
    382 
    383 Idea: [EternalAlexander](/profile/EternalAlexander "Master EternalAlexander")
    384 
    385 **Tutorial**
    386 
    387 First, let's choose an arbitrary root for the tree. Then for all pairs of paths, their LCA (lowest common ancestor) can be either different or the same.
    388 
    389 Then, let's calculate the answer of pairs with different LCAs. In this case, if the intersection is not empty, it will be a vertical path as in the graph below.
    390 
    391 ![ ](/predownloaded/95/e5/95e531fd6d6710c30f67f54a3a70332bfdde45a0.png)
    392 
    393 Here path $G-H$ and path $E-F$ intersects at path $B-G$.
    394 
    395 We can process all paths in decreasing order of the depth of their LCA. When processing a path $p$ we calculate the number of paths $q$, where $q$ is processed before $p$, and the edge-intersection of $p$ and $q$ is at least $k$. To do this we can plus one to the subtree of the nodes on the path $k$ edges away from the LCA (node $C$ and $D$ for path $G-H$ in the graph above), then we can query the value at the endpoints of the path (node $E$ and $F$ for path $E-F$). We can maintain this easily with BIT (binary indexed tree, or Fenwick tree).
    396 
    397 Next, we calculate pairs with the same LCA. This case is harder.
    398 
    399 For each node $u$ we calculate the number of pairs with the LCA $u$.
    400 
    401 ![ ](/predownloaded/fc/a0/fca00e8fdae5ddc2e82355dea768994e4315cc50.png)
    402 
    403 For a pair of path $(x_1,y_1)$ and $(x_2, y_2)$, there are still two cases we need to handle.
    404 
    405 Let $dfn_x$ be the index of $x$ in the DFS order. For a path $(x,y)$ we assume that $dfn_x \lt dfn_y$ (otherwise you can just swap them)
    406 
    407 In the first case ( the right one in the graph above, where $(x_1,y_1) = (B,E), (x_2,y_2) = (C,F)$ ), the intersection of $(x_1,y_1)$ and $(x_2,y_2)$ is the path that goes from $\operatorname{LCA}(x_1,x_2)$ to $\operatorname{LCA}(y_1,y_2)$ (path $A - D$)
    408 
    409 In this case the intersection may cross over node $u$.
    410 
    411 For all paths $(x,y)$ with the LCA $u$. We can build a virtual-tree over all $x$ of the paths, and on node $x$ we store the value of $y$. Let's do a dfs on the virtual-tree. On each node $a$ we calculate pairs $(x_1,y_1)$,$(x_2,y_2)$ that $\operatorname{LCA}(x_1,x_2) = a$. For $x_1$ , let's go from $a$ to $y_1$ for $k$ edges, assume the node we reached is $b$, all legal $y_2$ should be in the subtree of $b$.
    412 
    413 We can use a segment tree on the DFS-order to maintain all $y$s in the subtree and merge them with the small-to-large trick, meanwhile, iterate over all $x_1$ in the smaller segment tree, count the valid $y_2$'s in the larger segment tree.
    414 
    415 In fact, you can use HLD (heavy-light decomposition) instead of virtual-tree, which seems to be easier to implement.
    416 
    417 Now note that the solution above is based on the fact that the intersection of $(x_1,y_1)$ and $(x_2,y_2)$ is the path that goes from $\operatorname{LCA}(x_1,x_2)$ to $\operatorname{LCA}(y_1,y_2)$. But it is not always true, so here we have another case to handle.
    418 
    419 In this case, (the left one in the graph above), the intersection is definitely a vertical path that goes from $u$ to $\operatorname{LCA(y_1,x_2)}$. This can be solved similarly to the case of different LCAs.
    420 
    421 The overall complexity of this solution is $O(m \log^2 m + n\log n)$.
    422 
    423 **Solution by EternalAlexander**
    424 
    425 ```
    426 #include <bits/stdc++.h>
    427 #define maxn 200005
    428 int n,m,k,u[maxn],v[maxn],ch[maxn<<6][2]={0},sum[maxn<<6]={0},pt[maxn],head[maxn]={0},tail=0,cnt=0,root[maxn]={0},
    429 anc[maxn][19]={0},son[maxn]={0},depth[maxn]={0},dfn[maxn],size[maxn],idx=0;
    430 long long ans=0;
    431 std::vector<int>in[maxn],vec[maxn];
    432 struct edge {
    433 	int v,next;
    434 }edges[maxn<<1];
    435 void add_edge(int u,int v){
    436 	edges[++tail].v=v;
    437 	edges[tail].next=head[u];
    438 	head[u]=tail;
    439 }
    440 namespace BIT {
    441 	int sum[maxn<<2]={0};
    442 	void add(int p,int x) {if (p==0) return;while (p<=n) {sum[p]+=x;p+=p&-p;}}
    443 	int query(int p) {int ans=0;while (p>0) {ans+=sum[p];p-=p&-p;}return ans;}
    444 	void Add(int l,int r){add(l,1);add(r+1,-1);}
    445 }
    446 void update(int x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]];}
    447 int insert(int rt,int l,int r,int p){
    448 	if (!rt) rt=++cnt;
    449 	if (l==r) {sum[rt]++;return rt;}
    450 	int mid=(l+r)>>1;
    451 	if (p<=mid) ch[rt][0]=insert(ch[rt][0],l,mid,p);
    452 	else ch[rt][1]=insert(ch[rt][1],mid+1,r,p);
    453 	update(rt);
    454 	return rt;
    455 } int merge(int u,int v){
    456 	if (!u||!v)return u+v;
    457 	ch[u][0]=merge(ch[u][0],ch[v][0]);
    458 	ch[u][1]=merge(ch[u][1],ch[v][1]);
    459 	sum[u]=sum[u]+sum[v];return u;
    460 } int query(int rt,int L,int R,int l,int r){
    461 	if (l>R||r<L)return 0;
    462 	if (l<=L&&R<=r){return sum[rt];}
    463 	return query(ch[rt][0],L,(L+R)>>1,l,r)+query(ch[rt][1],((L+R)>>1)+1,R,l,r);
    464 }
    465 
    466 void dfs1(int u,int f){
    467 	anc[u][0]=f;depth[u]=depth[f]+1;size[u]=1;
    468 	for (int i=1;i<=18;++i)anc[u][i]=anc[anc[u][i-1]][i-1];
    469 	for (int i=head[u];i;i=edges[i].next){
    470 		int v=edges[i].v;
    471 		if (v==f) continue;
    472 		dfs1(v,u);size[u]+=size[v];
    473 		if (size[v]>size[son[u]])son[u]=v;
    474 	}
    475 } void dfsn(int u){
    476 	dfn[u]=++idx;
    477 	for (int i=head[u];i;i=edges[i].next){
    478 		int v=edges[i].v;
    479 		if (v==son[u]||v==anc[u][0])continue;
    480 		dfsn(v);
    481 	}if (son[u]) dfsn(son[u]);
    482 }
    483 
    484 int lift(int u,int x){
    485 	for (int i=18;i>=0;i--)if (x>=(1<<i)) {u=anc[u][i];x-=(1<<i);}
    486 	return u;
    487 }
    488 
    489 int lca(int u,int v){
    490 	if (depth[u]<depth[v])std::swap(u,v);
    491 	for (int i=18;i>=0;i--)if (depth[anc[u][i]]>=depth[v])u=anc[u][i];
    492 	if (u==v)return u;
    493 	for (int i=18;i>=0;i--)if (anc[u][i]!=anc[v][i]){u=anc[u][i];v=anc[v][i];}
    494 	return anc[u][0];
    495 } 
    496 
    497 void dfs3(int x,int rt){
    498 	pt[x]=x;root[x]=0;
    499 	for (int i=0;i<in[x].size();++i) {
    500 		int d=in[x][i];
    501 		int rd=std::max(0,k-(depth[u[d]]-depth[rt]));
    502 		if (depth[v[d]]-depth[rt]>=rd){
    503 			int l=lift(v[d],depth[v[d]]-depth[rt]-rd);
    504 			ans+=query(root[x],1,n,dfn[l],dfn[l]+size[l]-1);
    505 		}root[x]=insert(root[x],1,n,dfn[v[d]]);
    506 	}for (int i=head[x];i;i=edges[i].next){
    507 		int t=edges[i].v;
    508 		if (t==anc[x][0]||(rt==x&&t==son[x])) continue;
    509 		dfs3(t,rt);
    510 		if (in[pt[x]].size()<in[pt[t]].size()){
    511 			std::swap(pt[x],pt[t]);
    512 			std::swap(root[x],root[t]);
    513 		}while (!in[pt[t]].empty()){
    514 			int d=in[pt[t]][in[pt[t]].size()-1];in[pt[t]].pop_back();
    515 			int rd=std::max(0,k-(depth[x]-depth[rt]));
    516 			if (depth[v[d]]-depth[rt]>=rd) {
    517 				int l=lift(v[d],(depth[v[d]]-depth[rt]-rd));
    518 				ans+=query(root[x],1,n,dfn[l],dfn[l]+size[l]-1);
    519 			}in[pt[x]].push_back(d);
    520 		}root[x]=merge(root[x],root[t]);
    521 	}
    522 }
    523 
    524 void dfs2(int x){
    525 	int len=vec[x].size();
    526 	for (int i=head[x];i;i=edges[i].next)if (edges[i].v!=anc[x][0])dfs2(edges[i].v);
    527 	for (int i=0;i<len;++i)ans+=BIT::query(dfn[v[vec[x][i]]]);
    528 	for (int i=0;i<len;++i){
    529 		int j=vec[x][i];
    530 		if (depth[v[j]]-depth[x]>=k) {
    531 			int l=lift(v[j],depth[v[j]]-depth[x]-k);
    532 			BIT::Add(dfn[l],dfn[l]+size[l]-1);
    533 		}
    534 	}for (int i=0;i<len;++i){ans+=BIT::query(dfn[u[vec[x][i]]]);in[u[vec[x][i]]].push_back(vec[x][i]);}
    535 	dfs3(x,x);
    536 	while (!in[pt[x]].empty())in[pt[x]].pop_back();
    537 	for (int i=0;i<len;++i){
    538 		int j=vec[x][i];
    539 		if (depth[u[j]]-depth[x]>=k) {
    540 			int l=lift(u[j],depth[u[j]]-depth[x]-k);
    541 			BIT::Add(dfn[l],dfn[l]+size[l]-1);
    542 		}
    543 	}
    544 }
    545 	
    546 int main(){
    547 	scanf("%d%d%d",&n,&m,&k);
    548 	for(int i=1;i<n;++i){
    549 		int u,v;
    550 		scanf("%d%d",&u,&v);
    551 		add_edge(u,v);
    552 		add_edge(v,u);
    553 	}dfs1(1,0);dfsn(1);
    554 	for (int i=1;i<=m;++i){
    555 		scanf("%d%d",&u[i],&v[i]);
    556 		if (dfn[u[i]]>dfn[v[i]]) std::swap(u[i],v[i]);
    557 		int l=lca(u[i],v[i]);
    558 		vec[l].push_back(i);
    559 	} dfs2(1);
    560 	std::cout<<ans;
    561 	return 0;
    562 }
    563 ```