codeforces-scrape

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

1957.md (30540B)


      1 Source: https://codeforces.com/blog/entry/128716
      2 
      3 # [1957A - Stickogon](/contest/1957/problem/A "Codeforces Round 940 (Div. 2) and CodeCraft-23")
      4 
      5 **Idea:** [keyurchd_11](/profile/keyurchd_11 "Master keyurchd_11")  
      6 **Problem Setting:** [shakr](/profile/shakr "Expert shakr") [lezirtin](/profile/lezirtin "Expert lezirtin")  
      7 **Editorial**: [shakr](/profile/shakr "Expert shakr") [TheRaja](/profile/TheRaja "Candidate Master TheRaja")
      8 
      9 There were a few solutions which passes pre-tests with the assumption that $a_i \leq n$. We apologize for the pre-tests on A not including this case.
     10 
     11 **Hint 1**
     12 
     13 To create the most polygons, you should use as few sticks as possible per polygon. What polygon has the least number of sides?
     14 
     15 **Solution**
     16 
     17 Tutorial is loading...
     18 
     19 **Rate this problem**
     20 
     21 * Great Problem
     22 * Ok Problem
     23 * Bad Problem
     24 * Didn't solve
     25 
     26 **C++ Code**
     27 
     28 ```
     29 #include <bits/stdc++.h>
     30 
     31 using namespace std;
     32 
     33 int main(){ 
     34   int t; 
     35   cin >> t;
     36   while(t--) {
     37     int n; 
     38     cin >> n; 
     39     vector<int> a(101, 0);
     40     for (int i = 0; i < n; i++) {
     41       int x; 
     42       cin >> x;
     43       a[x]++;
     44     }
     45     int sum = 0;
     46     for (auto& s : a) 
     47       sum += s / 3;
     48     cout << sum << "\n";
     49   }
     50 }
     51 ```
     52 
     53 # [1957B - A BIT of a Construction](/contest/1957/problem/B "Codeforces Round 940 (Div. 2) and CodeCraft-23")
     54 
     55 **Idea:** [akcube](/profile/akcube "Master akcube")  
     56 **Problem Setting:** [Prakul_Agrawal](/profile/Prakul_Agrawal "Specialist Prakul_Agrawal")  
     57 **Editorial**: [Prakul_Agrawal](/profile/Prakul_Agrawal "Specialist Prakul_Agrawal") [TheRaja](/profile/TheRaja "Candidate Master TheRaja")
     58 
     59 **Hint 1**
     60 
     61 Given that the sum is bounded, which bits could be set in the bitwise OR?
     62 
     63 **Solution**
     64 
     65 Tutorial is loading...
     66 
     67 **Rate this problem**
     68 
     69 * Great Problem
     70 * Ok Problem
     71 * Bad Problem
     72 * Didn't solve
     73 
     74 **C++ Code**
     75 
     76 ```
     77 #include <bits/stdc++.h>
     78 
     79 using namespace std;
     80  
     81 int main(){
     82     int t; 
     83     cin >> t;
     84     while(t--) {
     85         int n, k;
     86         cin >> n >> k;
     87         vector<int> a(n);
     88         if (n == 1) {
     89             a[0] = k;
     90         }
     91         else {
     92             int msb = 0;
     93             // find the msb of k
     94             for (int i = 0; i < 31; i++) {
     95                 if (k & (1 << i)) {
     96                     msb = i;
     97                 }
     98             }
     99             a[0] = (1 << msb) - 1;
    100             a[1] = k - a[0];
    101             for (int i = 2; i < n; i++) {
    102                 a[i] = 0;
    103             }
    104         }
    105         for (int i = 0; i < n; i++) {
    106             cout << a[i] << " ";
    107         }
    108         cout << "\n";
    109     }
    110     return 0;
    111 }
    112 ```
    113 
    114 # [1957C - How Does the Rook Move?](/contest/1957/problem/C "Codeforces Round 940 (Div. 2) and CodeCraft-23")
    115 
    116 **Idea:** [SilverTongue1729](/profile/SilverTongue1729 "Expert SilverTongue1729")  
    117 **Problem Setting:** [ppt1524](/profile/ppt1524 "Expert ppt1524") [GenghizKhan](/profile/GenghizKhan "Candidate Master GenghizKhan")  
    118 **Editorial**: [ppt1524](/profile/ppt1524 "Expert ppt1524") [TheRaja](/profile/TheRaja "Candidate Master TheRaja")
    119 
    120 There are 2 ways to approach the problem. The combinatorics approach is slightly more involved and might be more difficult to come up with.
    121 
    122 **Hint 1**
    123 
    124 You can ignore the exact positions of the rooks in the initial configurations. Only the number of free rows and columns matter.
    125 
    126 **Hint 2**
    127 
    128 For each move you can make, how does the number of free rows/columns change?
    129 
    130 **Solution**
    131 
    132 Tutorial is loading...
    133 
    134 **Alternate Solution**
    135 
    136 Altenatively, we can iterate on the number of type $1$ moves we play. Let's term this to be $c$.
    137 
    138 There are ${m\choose c}$ ways to choose the $c$ type $1$ moves. Now, we have $m - c$ rows/columns left, and this must be even (type 2 moves cannot exhaust an odd number of rows/columns).
    139 
    140 We can see that each of the $(m - c)!$ permutations of the remaining columns correspond to a set of moves we can play. For example, if we have the columns $(1, 4, 5, 6)$ remaining, a permutation $(4, 5, 6, 1)$ corresponds to playing the moves $(4, 5), (6, 1)$. However, if we simply count the number of permutations, we would also be counting the permutation $(6, 1, 4, 5)$, which corresponds to the same set of moves.
    141 
    142 To remove overcounting, we can just divide $(m - c)!$ by $((m - c)/2)!$ (removing the permutations of the pairs chosen).
    143 
    144 Hence, the answer becomes
    145 
    146 $\sum\limits_{c = 0}^m [(m - c) \bmod 2 = 0] {m \choose c} \frac{(m - c)!}{\left(\frac{m - c}{2}\right)!}$
    147 
    148 **Rate this problem**
    149 
    150 * Great Problem
    151 * Ok Problem
    152 * Bad Problem
    153 * Didn't solve
    154 
    155 **C++ Code**
    156 
    157 ```
    158 #include <bits/stdc++.h>
    159 using namespace std;
    160  
    161 int dp[(int) 3e5+5];
    162 const int MOD = 1e9 + 7;
    163  
    164 int main() {
    165     cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    166     int t; 
    167     cin >> t;
    168     while (t--) {
    169         int n, k;
    170         cin >> n >> k;
    171         int used = 0;
    172         for (int i = 0; i < k; i++) {
    173             int r, c; cin >> r >> c;
    174             used += 2 - (r == c);
    175         }
    176         int m = n - used;
    177         dp[0] = dp[1] = 1;
    178         for (int i = 2; i <= m; i++)
    179             dp[i] = (dp[i-1] + 2ll * (i-1) * dp[i-2] % MOD) % MOD;
    180         cout << dp[m] << "\n";    
    181     }
    182     
    183 }
    184 ```
    185 
    186 # [1957D - A BIT of an Inequality](/contest/1957/problem/D "Codeforces Round 940 (Div. 2) and CodeCraft-23")
    187 
    188 **Idea:** [fangahawk](/profile/fangahawk "Master fangahawk")  
    189 **Problem Setting:** [fangahawk](/profile/fangahawk "Master fangahawk") [shiven](/profile/shiven "Master shiven")  
    190 **Editorial**: [JadeReaper](/profile/JadeReaper "Candidate Master JadeReaper") [TheRaja](/profile/TheRaja "Candidate Master TheRaja")
    191 
    192 **Hint 1**
    193 
    194 How can you simplify the given inequality? Use the fact that the XOR of a number with itself is 0.
    195 
    196 **Hint 2**
    197 
    198 The inequality simplifies to $f(x, z) \oplus a_y \gt f(x, z)$. For a given $a_y$ what subarrays (that include $a_y$) would satisfy this?
    199 
    200 **Solution**
    201 
    202 First we may rewrite the inequality as $f(x, z) \oplus a_y \gt f(x, z)$. So, for each index $y$, we want to find the total number of subarrays that contain $y$ but whose $\text{xor}$ decreases when we include the contribution of $a_y$.
    203 
    204 Including $a_y$ in some subarray $[x, z]$ (where $x \le y \le z$) can make the $\text{xor}$ lower only when some set bit of $a_y$ cancels out an existing set bit in $f(x, y - 1) \oplus f(y + 1, z)$. Consider the most signicant set bit in $a_y$. Call this bit $i$. Including $a_y$ would decrease the subarray $\text{xor}$ in subarrays where $f(x, y - 1)$ has $i$ set while $f(y+1, z)$ is unset or vice-versa.
    205 
    206 Now, for the subarrays where both the prefix subarray ($[x \dots y - 1]$) as well as the suffix subarray ($[y + 1 \dots z]$) where either both have bit $i$ set or both have it unset, by including $a_y$, we increment the xor by at least $2^i$. Even if by including $a_y$, every other smaller bit gets unset (because of cancelling out with $a_y$), this sum of these decrements is still less than $2^i$ thereby resulting in an overall positive contribution by including $a_y$.
    207 
    208 **Rate this problem**
    209 
    210 * Great Problem
    211 * Ok Problem
    212 * Bad Problem
    213 * Didn't solve
    214 
    215 **C++ Code**
    216 
    217 ```
    218 #include <bits/stdc++.h>
    219 
    220 using namespace std;
    221 
    222 const int Z = 30;
    223 const int MAX_N = 1e5 + 3;
    224 int pref[Z][MAX_N][2];
    225 int suff[Z][MAX_N][2];
    226 
    227 void solve() {
    228     int n;
    229     cin >> n;
    230     vector<int> a(n + 1);
    231     for (int i = 1; i <= n; i++) cin >> a[i];
    232     for (int i = 0; i < Z; i++) suff[i][n + 1][0] = suff[i][n + 1][1] = 0;
    233     for (int i = 0; i < Z; i++) {
    234         for (int j = 1; j <= n; j++) {
    235             int t = !!(a[j] & (1 << i));
    236             for (int k = 0; k < 2; k++) pref[i][j][k] = (t == k) + pref[i][j - 1][k ^ t];
    237         }
    238         for (int j = n; j >= 1; j--) {
    239             int t = !!(a[j] & (1 << i));
    240             for (int k = 0; k < 2; k++) suff[i][j][k] = (t == k) + suff[i][j + 1][k ^ t];
    241         }
    242     }
    243     long long ans = 0;
    244     for (int i = 1; i <= n; i++) {
    245         int z = 31 - __builtin_clz(a[i]);
    246         ans += 1ll * pref[z][i - 1][1] * (1 + suff[z][i + 1][0]);
    247         ans += 1ll * (1 + pref[z][i - 1][0]) * suff[z][i + 1][1];
    248     }
    249     cout << ans << "\n";
    250 }
    251 
    252 int main() {
    253     int tc;
    254     cin >> tc;
    255     while (tc--)
    256         solve();
    257     return 0;
    258 }
    259 ```
    260 
    261 # [1957E - Carousel of Combinations](/contest/1957/problem/E "Codeforces Round 940 (Div. 2) and CodeCraft-23")
    262 
    263 **Idea:** [SilverTongue1729](/profile/SilverTongue1729 "Expert SilverTongue1729")  
    264 **Problem Setting:** [JadeReaper](/profile/JadeReaper "Candidate Master JadeReaper")  
    265 **Editorial**: [SilverTongue1729](/profile/SilverTongue1729 "Expert SilverTongue1729") [JadeReaper](/profile/JadeReaper "Candidate Master JadeReaper") [TheRaja](/profile/TheRaja "Candidate Master TheRaja")
    266 
    267 **Hint 1**
    268 
    269 For what values of $j$ is $C(i,j) \bmod j = 0$?
    270 
    271 **Hint 2**
    272 
    273 For all other values of $j$, how can you precompute the result?
    274 
    275 **Hint 3**
    276 
    277 To precompute, switch around the loop order.
    278 
    279 **Solution**
    280 
    281 The number of distinct ways you can select $k$ distinct numbers from the set {$1, 2, \ldots, i$} and arrange them in a line is $i(i-1)\cdots(i-k+1)$, and since arranging in a circle introduces rotational symmetry we have to divide by $k$, so we have $C(i,k) = \frac{i(i-1)\cdots(i-k+1)}{k}$.
    282 
    283 Therefore $C(i,j) \bmod j = \frac{i(i-1)\cdots(i-j+1)}{j} \bmod j$. Now since the numerator is a product of $j$ consecutive integers, atleast one of them will be divisible by $j$. More precisely the exact integer which will be divisible by $j$ will be $ j \times \lfloor \frac{i}{j} \rfloor$. Hence we can simplify the fraction by removing the denominator and replacing the term $ j \times \lfloor \frac{i}{j} \rfloor$ with $\lfloor \frac{i}{j} \rfloor$ in the numerator. Each of the other $j-1$ integers in the numerator, after applying $\bmod j$ would cover all integers from $1$ to $j-1$. Hence
    284 
    285 $C(i,j) \bmod j = \frac{i(i-1)\cdots(i-j+1)}{j} \bmod j = \left( (j-1)! \times \left\lfloor \frac{i}{j} \right\rfloor \right) \bmod j$
    286 
    287 Here we can notice that all proper factors of $j$ will occur in $(j-1)!$, so based on this we can tell that $C(i,j) \bmod j = 0$ for all composite numbers $j$ except $j=4$.
    288 
    289 We first can handle the case of $j$ being prime. Using Wilson's Theorem, we know that $(j-1)! \equiv -1 \bmod j$ when $j$ is prime. Hence
    290 
    291 $C(i,j) \bmod j = - \left\lfloor \frac{i}{j} \right\rfloor$
    292 
    293 Now we can reverse the order of loops to sum over all primes, and to calculate the contribution of each prime we can maintain a update array called $delta$.
    294 
    295 To calculate the contribution for a single prime $p$, we know that for all $n$ from $kp$ to $(k + 1)p - 1$ (for all $k$ such that $kp \lt 1e6$) the contribution would be $-k$. So, in the $delta$ array, we increment index $kp$ with $-k \bmod p$ and decrement index $(k + 1)p$ with $-k \mod p$. Now, when we perform a prefix sum on this $delta$ array, we obtain the correct contributions from all primes.
    296 
    297 For the case of $j=4$, we just need to handle it as a prime.
    298 
    299 **Rate this problem**
    300 
    301 * Great Problem
    302 * Ok Problem
    303 * Bad Problem
    304 * Didn't solve
    305 
    306 **C++ Code**
    307 
    308 ```
    309 #include <bits/stdc++.h>
    310  
    311 using namespace std;
    312  
    313 const int MOD = 1e9 + 7;
    314 const int MAX_N = 1e6 + 3;
    315 bitset<MAX_N> isprime;
    316 vector<int> primes;
    317  
    318 vector<int> eratosthenesSieve(int lim) {
    319     isprime.set();
    320     isprime[0] = isprime[1] = false;
    321     for (int i = 4; i < lim; i += 2) isprime[i] = false;
    322     for (int i = 3; i * i < lim; i += 2)
    323         if (isprime[i])
    324             for (int j = i * i; j < lim; j += i * 2) isprime[j] = false;
    325     vector<int> pr;
    326     for (int i = 2; i < lim; i++)
    327         if (isprime[i]) pr.push_back(i);
    328     return pr;
    329 }
    330  
    331 vector<int> ans(MAX_N, 0);
    332  
    333 signed main() {
    334     primes = eratosthenesSieve(MAX_N);
    335     vector<int> del(MAX_N, 0);
    336     // Handle the contribution for all primes
    337     for (auto &p: primes) {
    338         for (int curr = p; curr < MAX_N; curr += p) {
    339             int inc = (p - ((curr / p) % p)) % p;
    340             del[curr] = (del[curr] + inc) % MOD;
    341             if (curr + p < MAX_N) del[curr + p] = (del[curr + p] - inc + MOD) % MOD;
    342         }
    343     }
    344     //Special case of 4
    345     for (int curr = 4; curr < MAX_N; curr += 4) {
    346         int inc = (2 * (curr / 4)) % 4;
    347         del[curr] = (del[curr] + inc) % MOD;
    348         if (curr + 4 < MAX_N) del[curr + 4] = (del[curr + 4] - inc + MOD) % MOD;
    349     }
    350     int pref = 0;
    351     for (int i = 1; i < MAX_N; i++) {
    352         pref = (pref + del[i]) % MOD;
    353         ans[i] = (ans[i - 1] + pref) % MOD;
    354     }
    355     int tc;
    356     cin >> tc;
    357     while (tc--) {
    358         int n;
    359         cin >> n;
    360         cout << ans[n] << "\n";
    361     }
    362 }
    363 ```
    364 
    365 # [1957F1 - Frequency Mismatch (Easy Version)](/contest/1957/problem/F1 "Codeforces Round 940 (Div. 2) and CodeCraft-23")
    366 
    367 **Idea:** [fangahawk](/profile/fangahawk "Master fangahawk")  
    368 **Problem Setting:** [fangahawk](/profile/fangahawk "Master fangahawk")  
    369 **Editorial:** [akcube](/profile/akcube "Master akcube")
    370 
    371 **Hint 1**
    372 
    373 Let's try answering a different question. Given two multisets of elements how can we check if they differ? Hashing? How to multiset hash efficiently?
    374 
    375 **Hint 2**
    376 
    377 Okay if we can now differentiate two multisets of unequal elements, can we try to answer queries by inserting into these hypothetical multisets and binary search the differing point to identify the element?
    378 
    379 **Solution**
    380 
    381 Let's discuss how to hash a multiset of elements $a$, $b$ and $c$. Here, I will link you to a famous blog by [rng_58](/profile/rng_58 "Legendary Grandmaster rng_58") [Hashing and Probability of Collision](https://rng-58.blogspot.com/2017/02/hashing-and-probability-of-collision.html). Quoting, let's take a random integer $r$ from the interval $[0, MOD)$, and compute the hash $(r+a_1)(r+a_2)\dots(r+a_n)$. This is a polynomial of $r$ of degree $n$, so again from Schwartz-Zippel lemma, the collision probability is at most $\frac{n}{MOD}$. The nice thing about this construction is that we can compute rolling hashes using this idea fast. To make implementation easier, this bound applies for summing the random numbers as well. You can check [this](https://codeforces.com/blog/entry/85900#comment-736594) for proof.
    382 
    383 Let's try to answer a single query $(u_1, v_1, u_2, v_2)$ using binary search. We will solve this query in $nlog^2(n)$ using this idea. To check for some $mid$ in our binary search, we insert the values of all nodes which have values from $1$ to $mid$ into a data structure that we can query the path sum of $u$ to $v$ using. Querying path sum is a fairly standard problem that can be solved using BIT / Segment trees and ETT (Euler-Tour Trick). Now to solve this query, we only need to binary search and find the first vertex where the hashes differ for both the paths. This vertex is guaranteed to have mismatched frequency on the two paths since it's addition into the path multi-sets changed their hashes. So now we can solve a single query in $nlog^2(n)$ time using hashing + BIT / Segtree.
    384 
    385 Now to solve this problem for all $Q$ queries. We can use the idea of parallel binary search here to improve our idea to answering all $Q$ queries efficiently. We can run the binary search for all queries in parallel. For each iteration, sort queries by the current position of their $mid$ values. Then insert values from $1$ to $mid$ of the first query into the BIT and query range sum to determine for that particular query how to adjust $mid$. You can then move the $mid$ pointer to that of the next query and so on. This solution will run in $O(nlog(n) + qlog^2(n))$.
    386 
    387 **Upd:** Thanks to [IceKnight1093](/profile/IceKnight1093 "Master IceKnight1093") for pointing this out. If we just use a single `int` hash with a field size of $\approx 10^9$, it gives us a probability of failure of $\frac{1}{10^9}$ per query. Since we're doing somewhere of the order $10^6$ comparisons per hash representation, this gives a rough $1 - \Big(1 - \frac{1}{10^9}\Big)^{10^6} \approx 10^{-3}$ chance of failure. This is not a great bound theoretically speaking, but from a practical standpoint, it is a loose bound and it is extremely unlikely that this solution can be hacked. That said, if we want better theoretical bounds we can just use a hash with field size $\approx 10^{18}$ or use double hashing. Even if we were to query all ${n \choose 2}$ paths, the chance of collision is $\approx \frac{n^2}{10^{18}} \approx 10^{-8}$, which is more than good enough. TL's were set to allow double hashing solutions to pass comfortably.
    388 
    389 **Rate this problem**
    390 
    391 * Great Problem
    392 * Ok Problem
    393 * Bad Problem
    394 * Didn't solve
    395 
    396 **C++ Code**
    397 
    398 ```
    399 #include <bits/stdc++.h>
    400 using namespace std;
    401 
    402 const int MOD = 1e9 + 7;
    403 using ll = long long;
    404 using dbl = long double;
    405 //#define int ll
    406 
    407 using vi = vector<int>;
    408 using vvi = vector<vi>;
    409 using pii = pair<int, int>;
    410 using vii = vector<pii>;
    411 using vvii = vector<vii>;
    412 using vll = vector<ll>;
    413 
    414 #define ff first
    415 #define ss second
    416 #define pb push_back
    417 #define rep(i, a, b) for(int i = a; i < (b); ++i)
    418 #define all(x) begin(x), end(x)
    419 #define sz(x) (int)(x).size()
    420 #define tc int t; cin>>t; while(t--)
    421 #define fightFight cin.tie(0) -> sync_with_stdio(0)
    422 
    423 template<class T>
    424 struct RMQ {
    425     vector<vector<T>> jmp;
    426     RMQ(const vector<T>& V) : jmp(1, V) {
    427         for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
    428             jmp.emplace_back(sz(V) - pw * 2 + 1);
    429             rep(j,0,sz(jmp[k]))
    430                 jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
    431         }
    432     }
    433     T query(int a, int b) {
    434         assert(a <= b); // tie(a, b) = minimax(a, b)
    435         int dep = 31 - __builtin_clz(b-a+1);
    436         return min(jmp[dep][a], jmp[dep][b - (1 << dep) + 1]);
    437     }
    438 };
    439 
    440 struct LCA {
    441     int T = 0;
    442     vi st, path, ret; vi en, d;
    443     RMQ<int> rmq;
    444     LCA(vector<vi>& C) : st(sz(C)), en(sz(C)), d(sz(C)), rmq((dfs(C,0,-1), ret)) {}
    445     void dfs(vvi &adj, int v, int par) {
    446         st[v] = T++;
    447         for (auto to : adj[v]) if (to != par) {
    448             path.pb(v), ret.pb(st[v]);
    449             d[to] = d[v] + 1;
    450             dfs(adj, to, v);
    451         }
    452         en[v] = T-1;
    453     }
    454     bool anc(int p, int c) { return st[p] <= st[c] and en[p] >= en[c]; }
    455     int lca(int a, int b) {
    456         if (a == b) return a;
    457         tie(a, b) = minmax(st[a], st[b]);
    458         return path[rmq.query(a, b-1)];
    459     }
    460     int dist(int a, int b) { return d[a] + d[b] - 2*d[lca(a,b)]; }
    461 };
    462 
    463 template<const int mod>
    464 struct mint {
    465     constexpr mint(int x = 0) : val((x % mod + mod) % mod) {}
    466     mint& operator+=(const mint &b) { val += b.val; val -= mod * (val >= mod); return *this; }
    467     mint& operator-=(const mint &b) { val -= b.val; val += mod * (val < 0); return *this; }
    468     mint& operator*=(const mint &b) { val = 1ll * val * b.val % mod; return *this; }
    469     mint& operator/=(const mint &b) { return *this *= b.inv(); }
    470     mint inv() const {
    471         int x = 1, y = 0, t;
    472         for(int a=val, b=mod; b; swap(a, b), swap(x, y))
    473             t = a/b, a -= t * b, x -= t * y;
    474         return mint(x);
    475     }
    476     mint pow(int b) const {
    477         mint a = *this, res(1);
    478         for(; b; a *= a, b /= 2)  if(b&1) res *= a;
    479         return res;
    480     }
    481     friend mint operator+(const mint &a, const mint &b) {return mint(a) += b;}
    482     friend mint operator-(const mint &a, const mint &b) {return mint(a) -= b;}
    483     friend mint operator*(const mint &a, const mint &b) {return mint(a) *= b;}
    484     friend mint operator/(const mint &a, const mint &b) {return mint(a) /= b;}
    485     friend bool operator==(const mint &a, const mint &b) {return a.val == b.val;}
    486     friend bool operator!=(const mint &a, const mint &b) {return a.val != b.val;}
    487     friend bool operator<(const mint &a, const mint &b) {return a.val < b.val;}
    488     friend ostream& operator<<(ostream &os, const mint &a) {return os << a.val;}
    489     int val;
    490 };
    491 using Mint = mint<MOD>;
    492 
    493 template<typename... Ts, size_t... Is, typename F>
    494 void __op(index_sequence<Is...>, tuple<Ts...>& a, const tuple<Ts...>& b, F op) { ((get<Is>(a) = op(get<Is>(a), get<Is>(b))), ...); }
    495 #define OVERLOAD(OP, F) \
    496 template<typename... Ts> auto& operator OP##=(tuple<Ts...> &a, const tuple<Ts...> &b) { __op(index_sequence_for<Ts...>(), a, b, F<>{}); return a; } \
    497 template<typename... Ts> auto operator OP(const tuple<Ts...> &a, const tuple<Ts...> &b) { auto c = a; c OP##= b; return c; }
    498 OVERLOAD(+, plus) OVERLOAD(-, minus) OVERLOAD(*, multiplies) OVERLOAD(/, divides)
    499 
    500 constexpr int NUM_HASHES = 2; // *
    501 constexpr array<int, NUM_HASHES> mods = {127657753, 987654319}; // *
    502 template <size_t N = NUM_HASHES>
    503 constexpr auto mint_ntuple(const int &v) {
    504     return [&]<size_t... Is>(index_sequence<Is...>) { return make_tuple(mint<mods[Is]>(v)...); }(make_index_sequence<N>{}); }
    505 
    506 using HT = decltype(mint_ntuple(0));
    507 
    508 template<typename T>
    509 struct FT {
    510     vector<T> s;
    511     T def;
    512     FT(int n, T def) : s(n, def), def(def) {}
    513     void update(int pos, T dif) { // a[pos] += dif
    514         for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
    515     }
    516     T query(int pos) { // sum of values in [0, pos)
    517         pos++;
    518         T res = def;
    519         for (; pos > 0; pos &= pos - 1) res += s[pos-1];
    520         return res;
    521     }
    522 };
    523 
    524 struct Query {
    525     int u1, v1, u2, v2, k;
    526     int l, r, ans, i;
    527     int mid(){ return l + (r-l)/2; }
    528 };
    529 
    530 auto rng = std::mt19937(std::random_device()());
    531 constexpr const int MXN = 1e5+5;
    532 
    533 void solve(){
    534     int n; cin >> n;
    535     vi a(n); for(auto &x : a) cin >> x, x--;
    536     vvi adj(n);
    537     for(int i=0; i < n-1; i++){
    538         int u, v; cin >> u >> v; u--, v--;
    539         adj[u].pb(v); adj[v].pb(u);
    540     }
    541 
    542     int q; cin >> q;
    543     vector<Query> queries(q);
    544     int idx=0;
    545     for(auto &[u1, v1, u2, v2, k, l, r, ans, i] : queries) cin >> u1 >> v1 >> u2 >> v2 >> k, u1--, v1--, u2--, v2--, l=0, ans=-1, i=idx++;
    546 
    547     LCA lca(adj);
    548     vi uni(a); sort(all(uni)); uni.resize(unique(all(uni)) - uni.begin());
    549     vvi cnode(MXN);
    550     for(int v=0; v < n; v++) cnode[a[v]].pb(v);
    551     vector<HT> hash(MXN);
    552     for(auto &c : uni) hash[c] = {rng(), rng()};    
    553 
    554     auto get_ett = [&](vvi &adj){
    555         vi tin(n), tout(n);
    556         int timer = 0;
    557         function<void(int,int)> dfs = [&](int v, int p){
    558             tin[v] = timer++;
    559             for(auto &to : adj[v]) if(to != p) dfs(to, v);
    560             tout[v] = timer++;
    561         };
    562         dfs(0, -1);
    563         return make_pair(tin, tout);
    564     };
    565     auto [tin, tout] = get_ett(adj);
    566 
    567     for(auto &q : queries) q.r = sz(uni)-1;
    568 
    569     vi vis(MXN);
    570     for(int _=0; _<20; _++){
    571         FT<HT> st(2*n, mint_ntuple(0));
    572         sort(all(queries), [&](Query &a, Query &b) { return a.mid() < b.mid(); });
    573         for(int qq=0, cptr=0; qq < q; qq++) if(queries[qq].l <= queries[qq].r) {
    574             auto &[u1, v1, u2, v2, k, l, r, ans, i] = queries[qq];
    575             for(; cptr < sz(uni) and cptr <= queries[qq].mid(); cptr++){
    576                 for(auto &v : cnode[uni[cptr]])
    577                     st.update(tin[v], hash[uni[cptr]]), st.update(tout[v], mint_ntuple(0)-hash[uni[cptr]]);
    578                 vis[uni[cptr]] = true;
    579             }
    580 
    581             int lca1 = lca.lca(u1, v1), lca2 = lca.lca(u2, v2);
    582             HT r1 = st.query(tin[lca1]), r2 = st.query(tin[lca2]);
    583             HT hash1 = (st.query(tin[u1]) + st.query(tin[v1]) - (r1 + r1));
    584             if(vis[a[lca1]]) hash1 += hash[a[lca1]];
    585             HT hash2 = (st.query(tin[u2]) + st.query(tin[v2]) - (r2 + r2));
    586             if(vis[a[lca2]]) hash2 += hash[a[lca2]];
    587 
    588             if(hash1 != hash2){
    589                 ans = queries[qq].mid();
    590                 r = queries[qq].mid()-1;
    591             }
    592             else l = queries[qq].mid()+1;
    593         }
    594         for(auto &c : uni) vis[c] = false;
    595     }
    596     
    597     sort(all(queries), [&](Query &a, Query &b) { return a.i < b.i; });
    598     for(auto &[u1, v1, u2, v2, k, l, r, ans, i] : queries){
    599         if(ans == -1) cout << 0 << '\n';
    600         else cout << 1 << ' ' << uni[ans]+1 << '\n';
    601     }
    602 }
    603 signed main(){ 
    604     fightFight; 
    605     solve(); 
    606 }
    607 ```
    608 
    609 # [1957F2 - Frequency Mismatch (Hard Version)](/contest/1957/problem/F2 "Codeforces Round 940 (Div. 2) and CodeCraft-23")
    610 
    611 **Idea:** [fangahawk](/profile/fangahawk "Master fangahawk")  
    612 **Problem Setting:** [fangahawk](/profile/fangahawk "Master fangahawk")  
    613 **Editorial**: [fangahawk](/profile/fangahawk "Master fangahawk") [TheRaja](/profile/TheRaja "Candidate Master TheRaja")
    614 
    615 **Hint 1**
    616 
    617 How would you find the smallest element with different frequencies in two static arrays using a segment tree? Consider hashing.
    618 
    619 **Hint 2**
    620 
    621 Try extending this idea to finding the smallest element with different frequencies in two different paths on a tree. Think persistent data structures.
    622 
    623 **Hint 3**
    624 
    625 Once you solve that, you can be extend it to finding the k smallest elements.
    626 
    627 **Solution**
    628 
    629 Tutorial is loading...
    630 
    631 You can also use an idea similar to the hashing technique used in F1 to hash the segment tree nodes.
    632 
    633 **Rate this problem**
    634 
    635 * Great Problem
    636 * Ok Problem
    637 * Bad Problem
    638 * Didn't solve
    639 
    640 **C++ Code**
    641 
    642 ```
    643 #include <bits/stdc++.h>
    644 using namespace std;
    645  
    646 const int MOD1 = 1e9 + 7;
    647 const int MOD2 = 998244353;
    648 using ll = long long;
    649 using dbl = long double;
    650 //#define int ll
    651  
    652 using vi = vector<int>;
    653 using vvi = vector<vi>;
    654 using pii = pair<int, int>;
    655 using vii = vector<pii>;
    656 using vvii = vector<vii>;
    657 using vll = vector<ll>;
    658  
    659 #define ff first
    660 #define ss second
    661 #define pb push_back
    662 #define rep(i, a, b) for(int i = a; i < (b); ++i)
    663 #define all(x) begin(x), end(x)
    664 #define sz(x) (int)(x).size()
    665 #define tc int t; cin>>t; while(t--)
    666 #define fightFight cin.tie(0) -> sync_with_stdio(0)
    667 template<class T>
    668 struct RMQ {
    669     vector<vector<T>> jmp;
    670     RMQ(const vector<T>& V) : jmp(1, V) {
    671         for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
    672             jmp.emplace_back(sz(V) - pw * 2 + 1);
    673             rep(j,0,sz(jmp[k]))
    674                 jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
    675         }
    676     }
    677     T query(int a, int b) {
    678         assert(a <= b); // tie(a, b) = minimax(a, b)
    679         int dep = 31 - __builtin_clz(b-a+1);
    680         return min(jmp[dep][a], jmp[dep][b - (1 << dep) + 1]);
    681     }
    682 };
    683 struct LCA {
    684     int T = 0;
    685     vi st, path, ret; vi en, d;
    686     RMQ<int> rmq;
    687     LCA(vector<vi>& C) : st(sz(C)), en(sz(C)), d(sz(C)), rmq((dfs(C,1,-1), ret)) {}
    688     void dfs(vvi &adj, int v, int par) {
    689         st[v] = T++;
    690         for (auto to : adj[v]) if (to != par) {
    691             path.pb(v), ret.pb(st[v]);
    692             d[to] = d[v] + 1;
    693             dfs(adj, to, v);
    694         }
    695         en[v] = T-1;
    696     }
    697     bool anc(int p, int c) { return st[p] <= st[c] and en[p] >= en[c]; }
    698     int lca(int a, int b) {
    699         if (a == b) return a;
    700         tie(a, b) = minmax(st[a], st[b]);
    701         return path[rmq.query(a, b-1)];
    702     }
    703     int dist(int a, int b) { return d[a] + d[b] - 2*d[lca(a,b)]; }
    704 };
    705 template<const int mod>
    706 struct mint {
    707     constexpr mint(int x = 0) : val((x % mod + mod) % mod) {}
    708     mint& operator+=(const mint &b) { val += b.val; val -= mod * (val >= mod); return *this; }
    709     mint& operator-=(const mint &b) { val -= b.val; val += mod * (val < 0); return *this; }
    710     mint& operator*=(const mint &b) { val = 1ll * val * b.val % mod; return *this; }
    711     mint& operator/=(const mint &b) { return *this *= b.inv(); }
    712     mint inv() const {
    713         int x = 1, y = 0, t;
    714         for(int a=val, b=mod; b; swap(a, b), swap(x, y))
    715             t = a/b, a -= t * b, x -= t * y;
    716         return mint(x);
    717     }
    718     mint pow(int b) const {
    719         mint a = *this, res(1);
    720         for(; b; a *= a, b /= 2)  if(b&1) res *= a;
    721         return res;
    722     }
    723     friend mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
    724     friend mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
    725     friend mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
    726     friend mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }
    727     friend bool operator==(const mint &a, const mint &b) { return a.val == b.val; }
    728     friend bool operator!=(const mint &a, const mint &b) { return a.val != b.val; }
    729     friend bool operator<(const mint &a, const mint &b) { return a.val < b.val; }
    730     friend ostream& operator<<(ostream &os, const mint &a) { return os << a.val; }
    731     int val;
    732 };
    733 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    734 uniform_int_distribution<ll> rnd(20,10000);
    735 using Mint1 = mint<MOD1>;
    736 using Mint2 = mint<MOD2>;
    737 using Mint = pair<Mint1,Mint2>;
    738 const int N = 3e5 + 10, LOGN = 20;
    739 int p1, p2;
    740 int blen = 0;
    741 int L[N * LOGN], R[N * LOGN];
    742 Mint ST[N * LOGN], p_pow[N];
    743 void prec() {
    744     p1 = rnd(rng);
    745     p2 = p1; 
    746     while (p2 == p1) p2 = rnd(rng);
    747     p_pow[0].ff = 1;
    748     p_pow[0].ss = 1;
    749     for (int i = 1; i < N; i++) {
    750         p_pow[i].ff = p_pow[i - 1].ff * p1;
    751         p_pow[i].ss = p_pow[i - 1].ss * p2;
    752     }
    753 }
    754 int update(int pos, int l, int r, int id) {
    755     if (pos < l || pos > r) return id;
    756     int ID = ++blen, m = (l + r) / 2;
    757     if (l == r) return (ST[ID] = {ST[id].ff + 1, ST[id].ss + 1}, ID);
    758     L[ID] = update(pos, l, m, L[id]);
    759     R[ID] = update(pos, m + 1, r, R[id]);
    760     return (ST[ID] = {ST[L[ID]].ff + p_pow[m - l + 1].ff * ST[R[ID]].ff, ST[L[ID]].ss + p_pow[m - l + 1].ss * ST[R[ID]].ss}, ID);
    761 }
    762 vi vals;
    763 using a4 = array<int,4>;
    764 void descent(int l, int r, const array<int, 4>& a, const array<int, 4>& b, int k) {
    765     if (l == r) return void(vals.push_back(l));
    766     int m = (l + r) / 2;
    767 #define stm(X, y) {ST[X[y[0]]].ff + ST[X[y[1]]].ff - ST[X[y[2]]].ff - ST[X[y[3]]].ff, ST[X[y[0]]].ss + ST[X[y[1]]].ss - ST[X[y[2]]].ss - ST[X[y[3]]].ss}
    768 #define arr(X, y) (a4{X[y[0]], X[y[1]], X[y[2]], X[y[3]]})
    769     Mint l1 = stm(L, a), l2 = stm(L, b), r1 = stm(R, a), r2 = stm(R, b);
    770     if (sz(vals) < k && l1 != l2) descent(l, m, arr(L, a), arr(L, b), k);
    771     if (sz(vals) < k && r1 != r2) descent(m + 1, r, arr(R, a), arr(R, b), k);
    772 }
    773  
    774 vvi adj;
    775 vi a, roots, par; 
    776 void dfs(int x, int p) {
    777     par[x] = p;
    778     roots[x] = update(a[x], 0, N, roots[par[x]]);
    779     for (auto& s : adj[x]) if (s != p) {
    780         dfs(s, x);
    781     }
    782 }
    783 void solve(){
    784     int n; cin >> n;        
    785     adj = vvi(n + 1);
    786     a = roots = par = vi(n + 1);
    787     for (int i = 1; i <= n; i++) cin >> a[i];
    788     for (int i = 0; i < n - 1; i++) {
    789         int a, b; cin >> a >> b;
    790         adj[a].pb(b), adj[b].pb(a);
    791     }
    792     dfs(1, 0);
    793     LCA lca(adj);
    794     int q; cin >> q;
    795     while (q--) {
    796         vals.clear();
    797         int u1, v1, u2, v2, k; cin >> u1 >> v1 >> u2 >> v2 >> k;
    798         int l1 = lca.lca(u1, v1), l2 = lca.lca(u2, v2);
    799         a4 a{roots[u1], roots[v1], roots[l1], roots[par[l1]]};
    800         a4 b{roots[u2], roots[v2], roots[l2], roots[par[l2]]};
    801         descent(0, N, a, b, k);
    802         cout << sz(vals) << " ";
    803         for (auto& s : vals) cout << s << " ";
    804         cout << "\n";
    805     }
    806 }
    807 signed main(){ 
    808     fightFight; 
    809     prec();
    810     solve(); 
    811 }
    812 ```