Tell me how you think.

# | User | Rating |
---|---|---|

1 | tourist | 3819 |

2 | Benq | 3745 |

3 | ksun48 | 3560 |

4 | Radewoosh | 3511 |

5 | Um_nik | 3489 |

6 | peehs_moorhsum | 3460 |

7 | Petr | 3414 |

8 | Miracle03 | 3410 |

9 | maroonrk | 3400 |

10 | sunset | 3338 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 207 |

2 | awoo | 181 |

2 | Errichto | 181 |

4 | Um_nik | 179 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 172 |

7 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

Tell me how you think.

Invented by DeadlyCritic.

$$$\mathcal Brief\;\mathcal Solution :$$$

A $$$n$$$-regular convex polygon is beautiful if and only if $$$n \% 4 = 0$$$. ($$$\%$$$ is the modular arithmetic symbol)

Tutorial is loading...

```
t = int(input())
for testcase in range(t):
n = int(input())
if(n%4 == 0) :
print("Yes")
else :
print("No")
```

```
#include <iostream>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
if(n % 4 == 0){
cout << "YES\n";
}
else cout << "NO\n";
}
}
```

Invented by DeadlyCritic.

$$$\mathcal Brief\;\mathcal Solution :$$$

If the string $$$s$$$ is non-decreasing, then the answer is $$$s$$$ itself, otherwise the answer is $$$x+1$$$ zeroes and $$$y$$$ ones, where $$$x$$$ is the number of leading zeroes of the string $$$s$$$, and $$$y$$$ is the number of trailing ones of the string $$$s$$$.

Tutorial is loading...

```
t = int(input())
for testcase in range(t):
n = int(input())
s = input()
lef, rig, sw = 1, 1, 0
for i in range(n-1):
if(s[i] > s[i+1]):
sw = 1
break
if(sw == 0):
print(s)
continue
for i in range(n):
if (s[i] == '1'):
lef = i
break
for i in range(n-1, 0, -1):
if (s[i] == '0'):
rig = i
break
st = s[:lef] + '0' + s[rig+1:]
print(st)
```

```
#include <iostream>
#include <string>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
string s;
cin >> s;
int sw = 1;
for(int i = 1; i < s.size(); i++){
if(s[i] < s[i-1])sw = 0;
}
if(sw){
cout << s << '\n';
continue;
}
string ans;
for(int i = 0; i < s.size(); i++){
if(s[i] == '1')break;
ans.push_back('0');
}
ans.push_back('0');
for(int i = s.size()-1; i >= 0; i--){
if(s[i] == '0')break;
ans.push_back('1');
}
cout << ans << '\n';
}
}
```

Invented by DeadlyCritic and adedalic.

$$$\mathcal Brief\; \mathcal Solution$$$ :

Give greatest elements to friends with $$$w_i = 1$$$. For the rest sort the elements in non-descending order of $$$a_i$$$ and sort the friends in non-ascending order of $$$w_i$$$ then give first $$$w_1-1$$$ elements to friend $$$1$$$, next $$$w_2-1$$$ elements to friend $$$2$$$ and so on, also give $$$k-i+1$$$-th greatest element to friend $$$i$$$ $$$(1 \le i \le k)$$$.

Tutorial is loading...

```
t = int(input())
for tc in range(t):
n, k = map(int, input().split())
a = list(map(int, input().split()))
w = list(map(int, input().split()))
a.sort(reverse = True)
w.sort()
ii, l, r = k, 0, n-1
ans = 0
for i in range(k):
if(w[i] > 1):
ii = i
break
ans = ans+a[l]*2
l = l+1
for u in range(k-1, ii-1, -1):
i = w[u]
ans = ans + a[l] + a[r]
r = r-i+1
l = l+1
print(ans)
```

```
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define int ll
using namespace std;
const int MN = 2e5+7;
vector<int> v[MN];
signed main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
for(int i = 0; i <= n; i++)v[i].clear();
ll a[n], w[k];
for(int i = 0; i < n; i++){
cin >> a[i];
}
for(int i = 0; i < k; i++){
cin >> w[i];
}
sort(w, w+k);
sort(a, a+n);
for(int i = 0; i < k/2; i++)swap(w[i], w[k-i-1]);
int po = 0;
for(int i = 0; i < n-k; i++){
while(w[po] == v[po].size()+1)po++;
v[po].push_back(a[i]);
}
ll ans = 0;
int qf = 1;
for(int i = 0; i < k; i++){
ans += a[n-i-1];
if(v[i].size())ans += v[i][0];
else ans += a[n-qf], qf++;
}
cout << ans << '\n';
}
}
```

Invented by DeadlyCritic.

$$$\mathcal Brief \mathcal Solution$$$ :

Realize that a RDB of level $$$i$$$ is consisted of a vertex (the root of the RDB of level $$$i$$$) connected to the roots of two RDBs of level $$$i-2$$$ and a RDB of level $$$i-1$$$.

Run a DP and calculate the answer for each level $$$i$$$ ($$$ 3 \le i \le 2 \cdot 10^6$$$), then $$$dp_i = 2 \cdot dp_{i-2} + dp_{i-1} + (i \% 3 == 0?4:0)$$$.

Tutorial is loading...

```
v = []
v.append(0)
v.append(0)
v.append(0)
v.append(4)
v.append(4)
mod = int(1e9+7)
for i in range (5, 2000010):
v.append(max(((2*v[i-2])+v[i-1])%mod,((4*v[i-4])+4*v[i-3]+v[i-2]+4)%mod))
t = int(input())
for _ in range(t):
print(v[int(input())])
```

```
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = int(1e9+7);
const int MN = int(2e6+7);
int dp[MN];
signed main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
dp[0] = dp[1] = 0;
dp[2] = 4;
for(int i = 3; i < MN; i++){
long long w = dp[i-1];
w += 2*dp[i-2] + (i % 3 == 2)*4;
w %= mod;
dp[i] = w;
}
int t;
cin >> t;
while(t--){
int n;
cin >> n;
n--;
cout << dp[n]%mod << '\n';
}
}
```

Challenge : Try solving problem D for $$$n \le 10^{18}$$$. (no matrix-multiplication)

Invented by DeadlyCritic.

$$$\mathcal Hints$$$ :

Find some greedy approaches. Its guessable that the problem is greedy.

Define $$$s_i$$$ for food $$$i$$$ equal to the number of guys who likes food $$$i$$$. Then find some condition which is enough to be sure that no answer exist.

See the last friend in a suitable permutation. What food will he eat?

Its easy to see that if $$$\forall 1 \le i \le m \Rightarrow s_i > w_i$$$, then no answer exist.

If a food $$$i$$$ exist such that $$$s_i \le w_i$$$, then what will happen to the friends who like this food? They can always eat this food no matter what happens, so lets call them as late as possible(so its less likely for them to eat more than one plate). Now continue the process with rest of the friends and foods.

$$$\mathcal Brief\;\mathcal Solution$$$ :

Define $$$s_i$$$ equal to the number of friends who likes food $$$i$$$. If for some $$$i$$$, $$$s_i \le w_i$$$ then place all the friends who likes food $$$i$$$ in the end of the permutation and erase them and continue doing the same thing for the rest of the friends and foods

It's easy to see that if the set of friends became empty then the permutation we constructed is suitable(and no one would eat Lee), otherwise Lee has to buy more food!!

Tutorial is loading...

```
import sys
import heapq
inputarray = [int(x) for x in sys.stdin.read().split()]
n, m = inputarray[0], inputarray[1]
s, w = [], []
for i in range(2, n+2):
w.append(inputarray[i])
g, eg, foodm, friendm, x, y = [], [], [], [], [], []
for i in range(n):
s.append(0)
foodm.append(0)
g.append([])
for i in range(m):
friendm.append(0)
x.append(0)
y.append(0)
inppo = n+2
for i in range(m):
x[i], y[i] = inputarray[inppo], inputarray[inppo+1]
inppo = inppo+2
x[i] = x[i]-1
y[i] = y[i]-1
u = x[i]
v = y[i]
s[u] = s[u]+1
s[v] = s[v]+1
g[u].append(i)
g[v].append(i)
eg.append((v, u))
myq = []
ans = []
for i in range(n):
heapq.heappush(myq, (-w[i]+s[i], i))
while len(myq):
u = myq[0]
heapq.heappop(myq)
if u[0] != -w[u[1]]+s[u[1]]:
continue
if(u[0] > 0):
print("DEAD")
sys.exit()
foodm[u[1]] = 1
sw = 1
for i in g[u[1]]:
if friendm[i] == 0:
friendm[i] = 1
if y[i] == u[1]:
x[i], y[i] = y[i], x[i]
s[x[i]] = s[x[i]]-1
s[y[i]] = s[y[i]]-1
heapq.heappush(myq, (-w[y[i]]+s[y[i]], y[i]))
ans.append(i)
if(len(ans) == m):
sw = 0
break;
if(sw == 0):
break
print("ALIVE")
for i in ans[::-1]:
print(i+1, end=" ")
```

```
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int MN = 2e5+7;
int x[MN], y[MN], s[MN], w[MN], mark[MN], colmark[MN];
vector<int> v[MN], a;
vector<pii> f;
priority_queue<pii, vector<pii>, greater<pii>> pq;
signed main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)cin >> w[i];
for(int i = 0; i < m; i++){
cin >> x[i] >> y[i];
s[x[i]]++;
s[y[i]]++;
v[x[i]].push_back(i);
v[y[i]].push_back(i);
}
for(int i = 1; i <= n; i++){
if(s[i])pq.push({max(0, s[i]-w[i]), i});
else colmark[i] = 1;
}
while(pq.size()){
auto q = pq.top();
pq.pop();
if(q.fr != max(0, s[q.sc]-w[q.sc]))continue;
if(q.fr > 0){
cout << "DEAD\n";
exit(0);
}
int id = q.sc;
vector<int> wt;
for(auto u : v[id]){
if(mark[u])continue;
a.push_back(u);
if(x[u] == id)
swap(x[u], y[u]);
if(!colmark[x[u]])wt.push_back(x[u]);
mark[u] = 1;
}
sort(all(wt));
for(int i = 0; i < wt.size(); i++){
s[wt[i]]--;
if(i == wt.size()-1 || wt[i+1] != wt[i]){
if(s[wt[i]]){
if(max(0, s[wt[i]]-w[wt[i]]) == 0)colmark[wt[i]] = 1;
pq.push({max(0, s[wt[i]]-w[wt[i]]), wt[i]});
}
}
}
}
cout << "ALIVE\n";
for(int i = 0; i < a.size()/2; i++)swap(a[i], a[a.size()-i-1]);
for(auto u : a){
cout << u+1 << ' ';
}
cout << '\n';
}
```

Invented by DeadlyCritic and AS.82.

$$$\mathcal Brief\; \mathcal Solution$$$ :

Define $$$win_{s,\,e}$$$ ($$$s \le e$$$) equal to $$$1$$$ if Lee can win the game when $$$s$$$ is written on the board, and equal to $$$0$$$ otherwise, also define $$$lose_{s,\,e}$$$ the same way.

Win :

If $$$e$$$ is odd then if $$$s$$$ is odd Lee loses otherwise Lee wins. So if $$$e$$$ is even then :

- if $$$\frac e 2 < s \le e$$$ then if $$$s$$$ is odd then Lee wins, otherwise Lee loses;
- if $$$\frac e 4 < s \le \frac e 2$$$ then Lee wins;
- if $$$s \le \frac e 4$$$ then the answer is equal to $$$win_{s,\, \lfloor \frac e 4 \rfloor}$$$.

Lose :

If $$$e < 2 \cdot s$$$, then Lee can immediately lose, otherwise the answer is equal to $$$\displaystyle win_{s,\, \lfloor \frac e 2 \rfloor}$$$.

Tutorial is loading...

```
import sys
inpy = [int(x) for x in sys.stdin.read().split()]
def win(s, e) :
if e == s :
return False
if e == s+1 :
return True
if e % 2 == 1 :
if s % 2 == 1 :
return False
return True
q = e//4
if s <= q :
return win(s, q)
q = e//2
if(s > q) :
return (e-s) % 2 == 1
return True
def lose(s, e) :
q = e//2
if(s > q) :
return True
else :
return win(s, q)
t = inpy[0]
start = (True, False)
inpo = 1
v = (True, True)
for tc in range(t):
if(inpo+1 >= len(inpy)) :
print('wtf')
s, e = inpy[inpo], inpy[inpo+1]
inpo = inpo+2
v = ((win(s, e), lose(s, e)))
if start[0] and start[1] :
break
if (not start[0]) and (not start[1]) :
break
if start[1] :
v = (not v[0], not v[1])
start = (v[1], v[0])
if((start[0] != True and start[0] != False) or (start[1] != True and start[1] != False)) :
print('wtf')
sw = 2
if start[1] :
sw = sw-1
print(1, end = ' ')
else :
sw = sw-1
print(0, end = ' ')
if start[0] :
print(1)
sw = sw-1
else :
print(0)
sw = sw-1
if sw :
print(wtf)
```

```
#include <iostream>
#include <vector>
#include <string>
#define fr first
#define sc second
#define ll long long
#define int ll
using namespace std;
const int MN = 1e5+7;
pair<int, int> c[MN];
int chk(ll s, ll e){
if(e == s)return 0;
if(e == s+1)return 1;
if(e & 1){
if(s & 1)return 0;
return 1;
}
if(s <= e/4)
return chk(s, e/4);
if(s > (e/4)*2)return ((e-s)&1);
else return 1;
}
int lck(ll s, ll e){
if(s*2 > e)return 1;
int w = e/2 + 3;
while(w*2 > e)w--;
return chk(s, w);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int n;
cin >> n;
for(int i = 0; i < n; i++){
ll x, y;
cin >> x >> y;
c[i] = {chk(x, y), lck(x, y)};
}
int f = 1;
int s = 0;
for(int i = 0; i < n; i++){
if(f == 1 && s == 1)break;
if(f == 0 && s == 0)break;
if(s == 1) c[i].fr^=1, c[i].sc^=1;
f = c[i].sc;
s = c[i].fr;
}
cout << s << ' ' << f << '\n';
}
```

Tutorial of Codeforces Round #652 (Div. 2)

Hi community,

I'm glad to invite you to my first contest, Codeforces Round #652 (Div. 2) which will be held at 23.06.2020 17:05 (Московское время) ($$$\text{notice the unusual time}$$$). The problems are mainly prepared and invented by me. The round is rated for participants with rating strictly less than $$$2100$$$, others are able to take part in the round out of competition. You will be given $$$2$$$ $$$\text{hours}$$$ to solve $$$6$$$ $$$\text{problems}$$$.

Firstly I'd like to thank adedalic for coordinating and reviewing the round, as well as helping with many different things.

I'd like to thank antontrygubO_o, physics0523, McDic, Ashishgup, dannyboy20031204, Kuzey, SinaSahabi, FieryPhoenix, ma_da_fa_ka, ITDOI, AM_I_Learning, awoo, lynmisakura, JustasLe and ArimeZ for testing the round and giving valuable feedback.

Also I'd like to thank coauthors, amiralisalimi, AS.82 and davooddkareshki for helping me with inventing and choosing the problems.

Finally, thanks to MikeMirzayanov for very nice and convenient Codeforces and Polygon platforms.

I wish you all will find the problems interesting, thank you for participating, and good luck!

$$$\text{Scoring distribution : } \; 500 ~- 1000 ~- 1500 ~- 2000 ~- 2500 ~- 3000$$$

$$$\textbf{UPD}$$$ : Editorial is out

Announcement of Codeforces Round #652 (Div. 2)

In the name of God;

Hi, here I want to suggest some random functions for Testlib.

Testlib has nice random functions, here I want to suggest some other ones. The first and the second random functions are available in testlib, but the rest are not.

1, $$$\text{rnd.next(l, r)}$$$, it will return a random number in range $$$l$$$ to $$$r$$$ with equal weights :

2, $$$\text{rnd.wnext(l, r, w)}$$$, it will return a random number in range $$$l$$$ to $$$r$$$ with monotonically increasing/decreasing weights depending on $$$w$$$ :

If $$$w = 0$$$ then it will be equal to $$$\text{rnd.next(l, r)}$$$.

If $$$w > 0$$$ :

If $$$w < 0$$$ :

3, $$$\text{rnd.cnext(l, r, c)}$$$, it will return a random number in range $$$l$$$ to $$$r$$$ :

If $$$c = 0$$$ then it will be equal to $$$\text{rnd.next(l, r)}$$$

If $$$c > 0$$$ :

If $$$c < 0$$$ :

4, $$$\text{rnd.cnext(l, r, c1, c2)}$$$, it will return a random number in range $$$l$$$ to $$$r$$$ like $$$\text{rnd.cnext(l, r, c)}$$$, but its not centered around $$$\frac {r+l} 2$$$ : ($$$c1 \ge 0$$$ and $$$c2 \ge 0$$$)

About the implementation of $$$\text{cnext(l, r, c1, c2)}$$$, its as follow :

Choose $$$c1+c2+1$$$ random numbers in rage $$$l$$$ to $$$r$$$ and sort them.

Return $$$c1+1$$$-th one.

As you can see if $$$c1 = c2$$$ then its equal to $$$\text{cnext(l, r, c1)}$$$.

If $$$c1 = 0$$$ then it will be equal to $$$\text{wnext(l, r, -c2)}$$$, if $$$c2 = 0$$$ then it will be equal to $$$\text{wnext(l, r, c1)}$$$.

Please share your suggestions in the comment section.

We have an array( $$$a$$$ ) of length $$$n$$$, all the elements are less than or equal to $$$n$$$, then we have to answer $$$q$$$ queries, each will be three numbers $$$x$$$, $$$l$$$, $$$r$$$, then you have to print $$$\displaystyle\sum\limits_{l \le i mod x \le r}a_i$$$, i.e print the sum of all $$$a_i$$$ for $$$1 \le i \le n$$$ and $$$i$$$ mod $$$x$$$ is in range $$$[l \cdot \cdot r]$$$.

$$$0 \le l \le r < x \le n$$$

Then what if we had queries to add a range?

The first query can be changed a little bit, it can be like we have $$$k$$$, $$$x$$$, $$$l$$$, $$$r$$$, then print the same number but with $$$i > k$$$.

$$$0 \le k < n$$$

Please share the solutions.

Halo :D!

Story: It was 4 AM and I was unable to sleep so I brought you a nice trick and a couple of problems to practice it.

*(Our DP changes if we change the root of the tree, otherwise it won't make any sense to use this trick)*

Let's say we want to find $$$dp_v$$$ for every vertex in a tree, we must be able to update $$$dp_v$$$ using the children of vertex $$$v$$$. Then the trick allows you to move the root from a vertex to one of its adjacent vertices in $$$O(1)$$$.

First, calculate DP when the root is some vertex $$$rat$$$. Its obvious that if we change root $$$r$$$ to one of its adjacent vertices, $$$v$$$, then only $$$dp_r$$$ and $$$dp_v$$$ can change, so that we can update $$$dp_r$$$ using its new children and last $$$dp_r$$$, also $$$dp_v$$$ can be updated the same way. It really depends on the DP.

*Note:*

*Don't iterate over children of vertices when moving the root, it will be $$$O(\sum\limits_v\binom{d_v}{2})$$$ and $$$W(n^2)$$$ so just don't. ($$$d_v$$$ is the degree of vertex $$$v$$$)*

Now being able to move the root with distance one, we will run a DFS from $$$rat$$$, and move the root with DFS.

See the semi-code below, i hope it helps for better understanding:

```
void dfs(int nw, int parent){
int fixDPnow = dp[nw], fixDPv;
for(v in children of nw){//skip v == parent
fixDPv = dp[v];
move(nw, v);//it will move the root from nw to v and updates dp
dfs(v, nw);
//following two lines will move the root to nw and update dp
dp[v] = fixDPv;
dp[nw] = fixDPnow;
}
}
int main(){
calculateDP(rat);//it will calculate the DP when the root is rat
dfs(rat, rat);//this will move the root to all the vertices
}
```

I can't open some of the problems so there is no solution for them, sorry.

You can read the same trick here, also the site has some problems.

Please comment problems that *can* be solved using this trick.

Let's say that the problem has online queries, such that each query gives two vertices $$$r$$$ and $$$v$$$ and wants you to calculate $$$f(r, v)$$$, it's equal to $$$dp_v$$$ when the root is $$$r$$$. It can be solved with rerooting + ancestors binary lifting, it will answers each query in $$$O(Q*log_2n)$$$ time($$$O(log_2n)$$$ for binary lifting), and also $$$O(n*log_2n)$$$ precalculation.

So lets see how it works, for every edge($$$v \to u$$$) find $$$dp_v$$$ if the root is $$$u$$$ and $$$dp_u$$$ if the root is $$$v$$$, it will take $$$O(n)$$$ time and $$$O(n)$$$ memory, and also for each vertex $$$v$$$, store $$$f(v, v)$$$. Then if the query is in form $$$v$$$ and $$$v$$$(i.e. it wants to find $$$dp_v$$$ such that the tree is rooted at vertex $$$v$$$ itself) then the answer will be $$$f(v, v)$$$, which is calculated in advance, otherwise the problem is reduced to the following problem:

You are given two vertices $$$r$$$ and $$$u$$$$$$(u \ne r)$$$ what is the second vertex in the unique path from $$$u$$$ to $$$r$$$(it means we want to find out which vertex is adjacent to $$$u$$$ and is the closest to $$$r$$$).

This problem can be solved using binary lifting, if $$$u$$$ is not an ancestor of $$$r$$$, then the answer is $$$u$$$'s parent(the root is vertex $$$rat$$$), otherwise, move $$$r$$$ using binary lifting until it's depth is equal to $$$u$$$'s depth plus 1, it can be done in $$$O(log_2n)$$$, let the answer to the reduced problem be $$$z$$$, then the answer to the whole query is equal to $$$f(z, u)$$$ such that $$$z$$$ is adjacent to $$$u$$$, we have already calculated it.

See the semi-code below, i skipped some parts so i will use $$$moveto(nw,\,u)$$$ to move the root from $$$nw$$$ to $$$u$$$, $$$f(r, u)$$$ for $$$dp_u$$$ when the root is $$$r$$$ and $$$rise(r,\,u)$$$ to find the ancestor of $$$r$$$ with depth equal to $$$depth_u+1$$$ in $$$O(log_2n)$$$.

```
void dfs(int nw, int parent){
store dp[nw] as the answer to f(nw, nw);
int fdpnw = dp[nw], fdpu;
for(u in children of nw){//skip u == parent
fdpu = dp[u];
store dp[u] as the answer to f(nw, u);
moveto(nw, u);//moving root to u
store dp[nw] as the answer to f(u, nw);
dfs(u, nw);//calculate the data for all vertices in the subtree of u
dp[nw] = fdpnw; dp[u] = fdpu;//moving root to nw
}
}
int main(){
calculateDP(1);//calculates dp when root is 1
dfs(1, 1);//it will move the root to all the vertices and calculates the data needed.
int q;
cin >> q;
while(q--){
int r, u;
cin >> r >> u;
if(r == u){
cout << f(r, u) << '\n'; //using the calculated data
continue;
}
if(u is not an ancestor of r){
cout << f(par[u], u) << '\n'; //using the calculated data
}
else{
r = rise(r, u);//its O(log_2n)
cout << f(r, u) << '\n'; //again using the calculated data
}
}
}
```

I tried to add a problem from polygon for the advanced part, the problem is completed but I couldn't bring it to Codeforces, but I give you the link for problem's package, it includes 50 tests, validator and checker, main correct solution and problem statement, you can try running them in polygon.

Windows Package(50 MB) Linux Package(45 MB)

Here is the complete implementation for the topic, $$$dp[u]$$$ is the size of the subtree of $$$u$$$ here.

```
#include <bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
const int MN = 2e5+7;
int dp[MN], dep[MN], timer, l, n, ans[MN], tin[MN], tout[MN];
vector<int> g[MN];
map<pair<int, int>, int> data;
vector<vector<int>> up;
bool is_ancestor(int u, int v){
return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
int rise(int u, int v){
if(dep[u] == dep[v]+1)return u;
int ln = dep[u] - dep[v] - 1;
int c = 0;
while(ln){
if(ln & 1)u = up[u][c];
ln >>= 1;
c++;
}
return u;
}
void cal(int nw, int pr){
dp[nw] = 1;
for(auto u : g[nw]){
if(u == pr)continue;
cal(u, nw);
dp[nw] += dp[u];
}
}
void store(int r, int u, int vl){
data[{r, u}] = vl;
}
void dfs(int nw, int pr){
int v = nw;
tin[v] = ++timer;
up[v][0] = pr;
for (int i = 1; (1 << i) <= dep[v]; ++i)
up[v][i] = up[up[v][i-1]][i-1];
for(auto u : g[nw]){
if(u == pr)continue;
dep[u] = dep[nw]+1;
int fdpnw = dp[nw], fdpu = dp[u];
store(nw, u, dp[u]);
dp[nw] -= dp[u];
dp[u] += dp[nw];
store(u, nw, dp[nw]);
dfs(u, nw);
dp[nw] = fdpnw;
dp[u] = fdpu;
}
tout[nw] = ++timer;
}
void preprocess(int root) {
l = ceil(log2(n));
up.assign(n, vector<int>(l + 1));
dfs(root, root);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int q;
cin >> n >> q;
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
cal(0, 0);
for(int i = 0; i < n; i++)ans[i] = dp[i];
preprocess(0);
while(q--){
int u, r;
cin >> r >> u;
r--; u--;
if(r == u){
cout << n << '\n';
continue;
}
if(is_ancestor(u, r)){
r = rise(r, u);
cout << data[{r, u}] << '\n';
}
else{
cout << ans[u] << '\n';
}
}
}
```

I used map to store the data, so the solution is a little slower than expected.

I hope it will help you with solving DP-Tree problems.

Thanks for your attention.

Nowadays tuns of people are in quarantine because of covid-19, so it increased visitors of lots of sites, including CF and caused CF' hosts to overload. So what should we do? In the time that we are bored of staying home and CF staffs(and problem setters) are doing they're best to bring us nice contests, what should we do to help them?

I know that some games' servers brought a feature that you can(if you want) use your computer as a host to help them(specially in Minecraft servers, they give you in-game items if you help them for example). I know it's a little forbidden to use this method but i think it will be much better if we could help CF that way, but it needs staffs attention to make it happen. Its a hard-to-do work but still worth it.

It can be used for example when CF servers are down, or they are overloading(it happens sometimes that lots of codes are submitted and are waiting for judgment), but sadly it will be harder to use this method in online contests, but truly a way to stop queueforces specially in system testing time after and normal times.

I believe lots of people are ready to help CF that way. Please let me know if you have any idea about how to help CF and decrease queueforces(not only after contests).

*Please comment below your ideas.*

The issue is as follow :

It happens when we(me and some of my friends) try to login to our account, after filling the boxes and pressing the button, then it shows a page saying the following page is not found, eror 404(i added an image below). For example it always happens when i try to enter my codeforces account using steam's in-game browser, and sometimes when using opera browser, it also happens when trying to use my gmail to login. Also it always happens when my friend try to enter his account using his mobile phone.

I hope it helped codeforces staffs to improve the site.

Its fixed now, really appreciate it, now i can play and code in the same time :D.

News coming up, i asked my friend to check if he still has the issue, the answer is yes, its fixed for me but sadly not for him, i hope response from staff, thanks in advance.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/02/2021 06:56:27 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|