codeforces-scrape

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

1255.md (21269B)


      1 Source: https://codeforces.com/blog/entry/71594
      2 
      3 [1255A - Изменение громкости](/contest/1255/problem/A "Codeforces Round 601 (Div. 2)")
      4 
      5 Author: [UncleGrandpa](/profile/UncleGrandpa "Мастер UncleGrandpa"). Prepared by [UncleGrandpa](/profile/UncleGrandpa "Мастер UncleGrandpa")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 [1255B - Замки для холодильников](/contest/1255/problem/B "Codeforces Round 601 (Div. 2)")
     12 
     13 Author: [I_love_tigersugar](/profile/I_love_tigersugar "Гроссмейстер I_love_tigersugar") ft. [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"). Prepared by [UncleGrandpa](/profile/UncleGrandpa "Мастер UncleGrandpa")
     14 
     15 **Tutorial**
     16 
     17 #### Modelize the problem
     18 
     19 We modelize the problem as graph, where each fridge is a vertex and each chain is an edge between two vertexes. The problem is now equivalent to: Given a graph with $n$ vertexes, each vertex has a value $a_i \ge 0$. We have to add $m$ edges to the graph such that each vertex is connected to at least two different vertexes and the total cost of edges added is minimum. The cost of an edge is the sum of value of its two end-points.
     20 
     21 #### Observe some basic properties of graph
     22 
     23 Now, each edge added will increase the sum of degree of all vertexes by 2. So adding m edges will make the sum of degree equal to $2 \times m$. Since each vertexes must be connected to at least $2$ other vertexes, the minimum sum of degree is $2 \times n$.
     24 
     25 * Case 1: $2\times m \lt 2\times n \Leftrightarrow m \lt n$
     26 
     27 In this case, it is obvious that the answer is $-1$.
     28 
     29 * Case 2: $2\times m = 2\times n \Leftrightarrow m=n$
     30 
     31 In this case, it is easy to see that the degree of each vertex will be exactly 2. As a result, no matter what edges we add, the result is still $2\times (a_1+a_2+...+a_n)$. But please take note that if $n=2$, then the answer will be $-1$ since for each vertex we have at most $1$ different vertex to connect to.
     32 
     33 * Case 3(Of the original, pre-modified version of the problem): $2\times m \gt 2\times n \Leftrightarrow m \gt n$
     34 
     35 Please read this [excellent answer](https://codeforces.com/blog/entry/71562?#comment-559266) by [Um_nik](/profile/Um_nik "Легендарный гроссмейстер Um_nik"). All credit goes to him for the excellent proof.
     36 
     37 [1255C - League of Leesins](/contest/1255/problem/C "Codeforces Round 601 (Div. 2)")
     38 
     39 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"). Prepared by [UncleGrandpa](/profile/UncleGrandpa "Мастер UncleGrandpa")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 [1254A - Кормление куриц](/contest/1254/problem/A "Codeforces Round 601 (Div. 1)")
     46 
     47 Author: [I_love_tigersugar](/profile/I_love_tigersugar "Гроссмейстер I_love_tigersugar"). Prepared by [I_love_tigersugar](/profile/I_love_tigersugar "Гроссмейстер I_love_tigersugar")
     48 
     49 **Tutorial**
     50 
     51 Tutorial is loading...
     52 
     53 **Source code**
     54 
     55 ```
     56 #include<bits/stdc++.h>
     57 #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
     58 #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
     59 #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
     60 #define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
     61 #define ALL(v) (v).begin(), (v).end()
     62 #define IS_INF(x)   (std::isinf(x))
     63 #define IS_NAN(x)   (std::isnan(x))
     64 #define fi   first
     65 #define se   second
     66 #define MASK(i) (1LL << (i))
     67 #define BIT(x, i) (((x) >> (i)) & 1)
     68 #define div   ___div
     69 #define next   ___next
     70 #define prev   ___prev
     71 #define left   ___left
     72 #define right   ___right
     73 #define __builtin_popcount __builtin_popcountll
     74 using namespace std;
     75 template<class X, class Y>
     76     bool minimize(X &x, const Y &y) {
     77         X eps = 1e-9;
     78         if (x > y + eps) {
     79             x = y;
     80             return true;
     81         } else return false;
     82     }
     83 template<class X, class Y>
     84     bool maximize(X &x, const Y &y) {
     85         X eps = 1e-9;
     86         if (x + eps < y) {
     87             x = y;
     88             return true;
     89         } else return false;
     90     }
     91 template<class T>
     92     T Abs(const T &x) {
     93         return (x < 0 ? -x : x);
     94     }
     95 
     96 /* Author: Van Hanh Pham */
     97 
     98 /** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/
     99 
    100 const string SYMBOLS = "QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm1234567890";
    101 
    102 #define MAX  111
    103 char board[MAX][MAX], res[MAX][MAX];
    104 int numRow, numCol, numChicken;
    105 
    106 void process(void) {
    107     memset(board, 0, sizeof board);
    108     memset(res, 0, sizeof res);
    109 
    110     scanf("%d%d%d", &numRow, &numCol, &numChicken);
    111     FOR(i, 1, numRow) scanf("%s", board[i] + 1);
    112 
    113     bool leftToRight = true;
    114     vector<pair<int, int>> cells;
    115     FOR(i, 1, numRow) {
    116         if (leftToRight) {
    117             FOR(j, 1, numCol) cells.push_back(make_pair(i, j));
    118         } else {
    119             FORD(j, numCol, 1) cells.push_back(make_pair(i, j));
    120         }
    121         leftToRight ^= 1;
    122     }
    123 
    124     int totRice = 0;
    125     FOR(i, 1, numRow) FOR(j, 1, numCol) if (board[i][j] == 'R') totRice++;
    126     int avg = totRice / numChicken;
    127     int diff = totRice % numChicken == 0 ? 0 : 1;
    128 
    129     REP(i, numChicken) {
    130         int cntRice = 0;
    131         while (true) {
    132             int x = cells.back().fi, y = cells.back().se;
    133             cells.pop_back();
    134             res[x][y] = SYMBOLS[i];
    135             if (board[x][y] == 'R') {
    136                 totRice--;
    137                 cntRice++;
    138             }
    139             if (cntRice < avg) continue;
    140             if (avg * (numChicken - i - 1) <= totRice && totRice <= (avg + diff) * (numChicken - i - 1)) break;
    141         }
    142     }
    143     while (!cells.empty()) {
    144         int x = cells.back().fi, y = cells.back().se;
    145         cells.pop_back();
    146         res[x][y] = SYMBOLS[numChicken - 1];
    147     }
    148 
    149     FOR(i, 1, numRow) {
    150         FOR(j, 1, numCol) printf("%c", res[i][j]); printf("\n");
    151     }
    152 }
    153 
    154 int main(void) {
    155     int t; scanf("%d", &t);
    156     REP(love, t) process();
    157     return 0;
    158 }
    159 
    160 /*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/
    161 ```
    162 
    163 [1254B1 - Отправьте коробки Алисе (упрощенная версия)](/contest/1254/problem/B1 "Codeforces Round 601 (Div. 1)")
    164 
    165 Author: [MofK](/profile/MofK "Международный гроссмейстер MofK"). Prepared by [UncleGrandpa](/profile/UncleGrandpa "Мастер UncleGrandpa")
    166 
    167 **Tutorial**
    168 
    169 The problem asked you to move chocolate pieces between adjacent boxes so that the number of chocolate pieces in all boxes is divisible by $k$ ($k \gt 1$).
    170 
    171 #### How to solve the problem for a specific $k$
    172 
    173 Now, it's clear that we will divide the array into segments, such that the sum of each segment is divisible by $k$, and move all chocolate pieces in that segment to a common box. Here we take notice of 2 things:
    174 
    175 * First, in each segment, let $A$ be the array of all position with 1, then the position that we move all the 1 to is the median of that array $A$ (easy to prove).
    176 * Second, the sum of each segment should be all equal to $k$. It's easy to see that if there exists some segment of sum $x*k$, then separating them into $x$ segments of sum $k$ will improve the result.
    177 
    178 With that two observations, we can iterate from 1 to n, push each position with value 1 into a temp array, and whenever the size of array become k, we add to our result the sum of $|a_i-median|$ and clear the array.
    179 
    180 #### Knowing how to solve for a specific $k$, how to solve the problem?
    181 
    182 It is clear that $k$ must be a divisor of the total number of chocolate pieces. So we iterate through all possible $k$ and minimize our answer with the number of steps to make all numbers divisible by k. A number $\le 10^5$ has at most 128 divisors, and each calculation take $O(n)$ so the solution should pass easily.
    183 
    184 **Source code**
    185 
    186 ```
    187 #include <bits/stdc++.h>
    188 
    189 using namespace std;
    190 
    191 const int maxn = 1000006;
    192 int n;
    193 int a[maxn];
    194 vector <int> v;
    195 
    196 long long cost(int p) {
    197     long long ret = 0;
    198     for (int i = 0; i < v.size(); i += p) {
    199         int median = v[(i + i + p - 1) / 2];
    200         for (int j = i; j < i + p; ++j)
    201             ret += abs(v[j] - median);
    202     }
    203     return ret;
    204 }
    205 
    206 int main(void) {
    207     ios_base::sync_with_stdio(0);
    208     cin.tie(NULL);
    209     cin >> n;
    210     for (int i = 1; i <= n; ++i) {
    211         cin >> a[i];
    212         if (a[i] == 1) v.push_back(i);
    213     }
    214     if (v.size() == 1) {
    215         cout << -1 << endl;
    216         return 0;
    217     }
    218     long long ans = 1e18;
    219     int tmp = v.size(), p = 2;
    220     while (p * p <= tmp) {
    221         if (tmp % p == 0) {
    222             ans = min(ans, cost(p));
    223             while (tmp % p == 0)
    224                 tmp /= p;
    225         }
    226         ++p;
    227     }
    228     if (tmp > 1)
    229         ans = min(ans, cost(tmp));
    230     cout << ans << endl;
    231     return 0;
    232 }
    233 ```
    234 
    235 [1254B2 - Отправьте коробки Алисе (усложнённая версия)](/contest/1254/problem/B2 "Codeforces Round 601 (Div. 1)")
    236 
    237 Author: [MofK](/profile/MofK "Международный гроссмейстер MofK"). Prepared by [MofK](/profile/MofK "Международный гроссмейстер MofK") and [UncleGrandpa](/profile/UncleGrandpa "Мастер UncleGrandpa")
    238 
    239 **Tutorial**
    240 
    241 The problem E2 is different from the problem E1 in some ways. Now all $A_i$ is at most $10^6$, and so is the number $n$. That makes our solution on E1 simply not usable in this problem.
    242 
    243 #### A cute observation:
    244 
    245 Let $S_i$ be the sum of $a_1 + a_2 + ... + a_i$. Now we see that:
    246 
    247 * if we move a chocolate piece from box $i$ to box $i+1$, it is equivalent to decrease $S_i$ by 1.
    248 * if we move a chocolate piece from box $i+1$ to box $i$, it is equivalent to increase $S_i$ by 1.
    249 
    250 Wow, now each moving steps only affect one number. Next, we can see that if every $a_i$ is divisible by k, then so is every $S_i$. Thus, our problem is now transformed to: Given an array $S$. At each turn, you can choose one $S_i$ and increase (or decrease) it by one (except for $S_n$). Find the minimum number of steps to make all $S_i$ divisible by $k$.
    251 
    252 #### How to solve the problem for a specific $k$
    253 
    254 An intuitive approach is to try to increase (or decrease) each $S_i$ to the nearest multiple of $k$. If such a configuration can be achieved then it will obviously be the best answer. The only concern is that: is there any scenario when there exists some $i$ such that $S_i \gt S_{i+1}$, which is indeed a violation? Fortunately, the answer is no. We can enforce the solution to iterate each $S_i$ from $1$ to $n-1$ and always choose to decrease if there is a tie. This way, the sequence $S$ will remain non-decreasing throughout the process.
    255 
    256 So, the solution is as follows. Just iterate from $1$ to $n-1$ and for each $i$, add to our result $min(S_i\%k,k-S_i\%k)$.
    257 
    258 #### Knowing how to solve for a specific $k$, how to solve the problem?
    259 
    260 Again, like E1, it is clear that $k$ must be a divisor of the total number of chocolate pieces. But now the total number of chocolate pieces is at most $10^{12}$, which an iteration through all divisors will not be fast enough to fit in 1 second. (In fact, we did make just one single test case to block this solution. Nevertheless, on random testcases it runs super fast).
    261 
    262 But if you have solved the problem to this phase already, you can easily realize that we only need to consider prime $k$, because if $k$ is composite then picking any prime divisors of it will lead to either a better result or an equal result.
    263 
    264 That's it, there will be at most 12 distinct prime divisors. Each calculation takes $O(n)$. So the solution will also pass easily.
    265 
    266 **Source code**
    267 
    268 ```
    269 #include <bits/stdc++.h>
    270 
    271 using namespace std;
    272 
    273 const int maxn = 1000006;
    274 int n;
    275 long long a[maxn];
    276 long long s[maxn];
    277 
    278 long long cost(long long mod) {
    279     long long ret = 0;
    280     for (int i = 1; i <= n; ++i)
    281         ret += min(s[i] % mod, mod - s[i] % mod);
    282     return ret;
    283 }
    284 
    285 int main(void) {
    286     ios_base::sync_with_stdio(0);
    287     cin.tie(NULL);
    288     cin >> n;
    289     for (int i = 1; i <= n; ++i) {
    290         cin >> a[i];
    291         s[i] = s[i-1] + a[i];
    292     }
    293     if (s[n] == 1) {
    294         cout << -1 << endl;
    295         return 0;
    296     }
    297     long long ans = 1e18;
    298     long long tmp = s[n], p = 2;
    299     while (p * p <= tmp) {
    300         if (tmp % p == 0) {
    301             ans = min(ans, cost(p));
    302             while (tmp % p == 0)
    303                 tmp /= p;
    304         }
    305         ++p;
    306     }
    307     if (tmp > 1)
    308         ans = min(ans, cost(tmp));
    309     cout << ans << endl;
    310     return 0;
    311 }
    312 ```
    313 
    314 [1254C - Упорядочьте точки](/contest/1254/problem/C "Codeforces Round 601 (Div. 1)")
    315 
    316 Author: [ngkan](/profile/ngkan "Мастер ngkan"). Prepared by [ngkan](/profile/ngkan "Мастер ngkan")
    317 
    318 **Tutorial**
    319 
    320 Tutorial is loading...
    321 
    322 **Source code**
    323 
    324 ```
    325 #include <bits/stdc++.h>
    326 using namespace std;
    327 
    328 int n;
    329 
    330 void check_if_zero(long long x){
    331     if (x == 0) exit(0);
    332 }
    333 
    334 long long get_area(int a,int b,int c){
    335     long long result;
    336     cout << 1 << ' ' << a << ' ' << b << ' ' << c << endl;
    337     cin >> result;
    338     check_if_zero(result);
    339     assert(result > 0);
    340     return result;
    341 }
    342 
    343 int get_sign(int o,int a,int b){
    344     int result;
    345     cout << 2 << ' ' << o << ' ' << a << ' ' << b << endl;
    346     cin >> result;
    347     check_if_zero(result);
    348     assert(abs(result) == 1);
    349     return result;
    350 }
    351 
    352 vector <int> lef, rig;
    353 
    354 void divide(){
    355     for(int i=3;i<=n;i++){
    356         int sign = get_sign(1, 2, i);
    357 
    358         if (sign == 1)
    359             lef.push_back(i);
    360         else
    361             rig.push_back(i);
    362     }
    363 }
    364 
    365 long long area12[1005];
    366 
    367 void _do(vector<int> &lst){
    368     if (lst.size() <= 1)
    369         return;
    370 
    371     long long best = 0;
    372     for(auto v: lst){
    373         area12[v] = get_area(1, 2, v);
    374         if (area12[v] > area12[best])
    375             best = v;
    376     }
    377 
    378     vector <int> l, r;
    379     for(auto v: lst){
    380         if (v == best)
    381             continue;
    382 
    383         if (get_sign(1, best, v) == 1)
    384             l.push_back(v);
    385         else
    386             r.push_back(v);
    387     }
    388 
    389     sort(l.begin(), l.end(), [&](int x,int y){
    390         return area12[x] > area12[y];
    391     });
    392     sort(r.begin(), r.end(), [&](int x,int y){
    393         return area12[x] < area12[y];
    394     });
    395 
    396     lst.clear();
    397     for(auto v: r)  lst.push_back(v);
    398     lst.push_back(best);
    399     for(auto v: l)  lst.push_back(v);
    400 }
    401 
    402 void answer(){
    403     cout << 0 << ' ' << 1 << ' ';
    404     for(auto v: rig)  cout << v << ' ';
    405     cout << 2 << ' ';
    406     for(auto v: lef)  cout << v << ' ';
    407     cout << endl;
    408 }
    409 
    410 int main(){
    411     cin >> n;
    412     assert(n >= 3);
    413 
    414     divide();   // n-2 queries
    415     _do(lef);
    416     _do(rig);   //  2*(n-2) - 1 or 2*(n-2) - 2 queries
    417     answer();
    418 }
    419 ```
    420 
    421 [1254D - Запросы на дереве](/contest/1254/problem/D "Codeforces Round 601 (Div. 1)")
    422 
    423 Author: [I_love_tigersugar](/profile/I_love_tigersugar "Гроссмейстер I_love_tigersugar") Prepared by [I_love_tigersugar](/profile/I_love_tigersugar "Гроссмейстер I_love_tigersugar")
    424 
    425 **Tutorial**
    426 
    427 Tutorial is loading...
    428 
    429 **Source code**
    430 
    431 ```
    432 #include <bits/stdc++.h>
    433  
    434 using namespace std;
    435  
    436 const int maxn = 150005;
    437 const int mod = 998244353;
    438 const int heavy = 300;
    439 int n, m, q;
    440 vector <int> adj[maxn];
    441 int dad[maxn];
    442 int sz[maxn];
    443 vector <int> pos[maxn];
    444 int tour[2*maxn];
    445 vector <int> heavy_vector;
    446 int weight[2*maxn];
    447  
    448 int pw(int x, int y) {
    449     int r = 1;
    450     while (y) {
    451         if (y & 1) r = 1LL * r * x % mod;
    452         x = 1LL * x * x % mod;
    453         y >>= 1;
    454     }
    455     return r;
    456 }
    457  
    458 void dfs(int u) {
    459     tour[++m] = u;
    460     pos[u].push_back(m);
    461     sz[u] = 1;
    462     for (auto v: adj[u]) {
    463         if (v == dad[u]) continue;
    464         dad[v] = u;
    465         dfs(v);
    466         sz[u] += sz[v];
    467         tour[++m] = u;
    468         pos[u].push_back(m);
    469     }
    470 }
    471  
    472 int fwt[2*maxn];
    473 void upd(int l, int r, int d) {
    474     for (int p = l; p <= m; p += p & -p) fwt[p] = (fwt[p] + d) % mod;
    475     ++r;
    476     for (int p = r; p <= m; p += p & -p) fwt[p] = (fwt[p] + mod - d) % mod;
    477 }
    478 int get(int p) {
    479     int ret = 0;
    480     for (; p; p -= p & -p) ret = (ret + fwt[p]) % mod;
    481     return ret;
    482 }
    483  
    484 int main(void) {
    485     ios_base::sync_with_stdio(0);
    486     cin.tie(NULL);
    487     cin >> n >> q;
    488     int inv_n = pw(n, mod - 2);
    489     for (int i = 1; i < n; ++i) {
    490         int u, v;
    491         cin >> u >> v;
    492         adj[u].push_back(v);
    493         adj[v].push_back(u);
    494     }
    495  
    496     dfs(1);
    497     for (int i = 1; i <= n; ++i) if (adj[i].size() >= heavy)
    498         heavy_vector.push_back(i);
    499  
    500     while (q--) {
    501         int type, v;
    502         cin >> type >> v;
    503         if (type == 1) {
    504             int d;
    505             cin >> d;
    506             weight[v] = (weight[v] + d) % mod;
    507             if (adj[v].size() < heavy) {
    508                 for (auto u: adj[v]) if (u != dad[v])
    509                     upd(pos[u][0], pos[u].back(), 1LL * d * (n - sz[u]) % mod * inv_n % mod);
    510                 if (v == 1) continue;
    511                 upd(1, pos[v][0] - 1, 1LL * d * sz[v] % mod * inv_n % mod);
    512                 upd(pos[v].back() + 1, m, 1LL * d * sz[v] % mod * inv_n % mod);
    513             }
    514         }
    515         else {
    516             int ans = (weight[v] + get(pos[v][0])) % mod;
    517             for (auto u: heavy_vector) {
    518                 if (u == v) continue;
    519                 auto it = lower_bound(pos[u].begin(), pos[u].end(), pos[v][0]);
    520                 if (it == pos[u].begin() || it == pos[u].end())
    521                     ans = (ans + 1LL * weight[u] * sz[u] % mod * inv_n) % mod;
    522                 else {
    523                     int p = tour[*(--it) + 1];
    524                     ans = (ans + 1LL * weight[u] * (n - sz[p]) % mod * inv_n) % mod;
    525                 }
    526             }
    527             cout << ans << '\n';
    528         }
    529     }
    530     return 0;
    531 }
    532 ```
    533 
    534 [1254E - Отправьте дерево Чарли](/contest/1254/problem/E "Codeforces Round 601 (Div. 1)")
    535 
    536 Author: [MofK](/profile/MofK "Международный гроссмейстер MofK") Prepared by: [MofK](/profile/MofK "Международный гроссмейстер MofK")
    537 
    538 **Tutorial**
    539 
    540 Tutorial is loading...
    541 
    542 **Source code**
    543 
    544 ```
    545 #include <bits/stdc++.h>
    546 
    547 using namespace std;
    548 
    549 const int mod = 1e9 + 7;
    550 const int maxn = 500005;
    551 
    552 int n;
    553 vector <int> adj[maxn];
    554 int a[maxn];
    555 int dad[maxn];
    556 int h[maxn];
    557 vector <pair <int, int> > conditions[maxn];
    558 int nxt[maxn], prv[maxn], seen[maxn];
    559 
    560 void no(int ncase) {
    561     cerr << ncase << endl;
    562     cout << 0 << endl;
    563     exit(0);
    564 }
    565 
    566 void dfs(int u) {
    567     for (auto v: adj[u]) if (v != dad[u]) {
    568         dad[v] = u;
    569         h[v] = h[u] + 1;
    570         dfs(v);
    571     }
    572 }
    573 
    574 int cnt; ///total distance, must not be more than 2n-2
    575 
    576 void go(int u, int v) {
    577     if (u == v) no(0);
    578     vector <int> from_u, to_v;
    579     ///naive LCA works here as long as we exit upon finding a conflict
    580     from_u.push_back(n + 1); ///first edge (fake)
    581     to_v.push_back(n + 2); ///last edge (fake)
    582     while (h[u] > h[v]) {
    583         from_u.push_back(u);
    584         u = dad[u];
    585     }
    586     while (h[v] > h[u]) {
    587         to_v.push_back(v);
    588         v = dad[v];
    589     }
    590     while (u != v) {
    591         from_u.push_back(u);
    592         u = dad[u];
    593         to_v.push_back(v);
    594         v = dad[v];
    595     }
    596     from_u.push_back(u);
    597     from_u.insert(from_u.end(), to_v.rbegin(), to_v.rend());
    598     for (int i = 1; i + 1 < from_u.size(); ++i)
    599         conditions[from_u[i]].push_back({from_u[i-1], from_u[i+1]});
    600     cnt += from_u.size() - 3;
    601     if (cnt > 2 * n - 2) no(0); ///important break
    602 }
    603 
    604 int main(void) {
    605     ios_base::sync_with_stdio(0);
    606     cin.tie(NULL);
    607     cin >> n;
    608     for (int i = 1; i < n; ++i) {
    609         int u, v;
    610         cin >> u >> v;
    611         adj[u].push_back(v);
    612         adj[v].push_back(u);
    613     }
    614     for (int i = 1; i <= n; ++i) {
    615         adj[i].push_back(n + 1); ///first edge (fake)
    616         adj[i].push_back(n + 2); ///last edge (fake)
    617     }
    618     for (int i = 1; i <= n; ++i) cin >> a[i];
    619 
    620     if (n == 1) {
    621         cout << 1 << endl;
    622         exit(0);
    623     }
    624 
    625     dfs(1);
    626     for (int i = 1; i <= n; ++i) if (a[i] != 0) go(i, a[i]);
    627 
    628     ///answer 0 if:
    629     ///1. there are 2 or more incoming/outgoing
    630     ///conditions to/from an edge, or
    631     ///2. there is a cycle, or
    632     ///3. first (n+1) is connected to last (n+2),
    633     ///but does not contain all other edges.
    634     int ans = 1;
    635     for (int i = 1; i <= n; ++i) {
    636         ///check case 1
    637         for (auto edge: conditions[i]) {
    638             int u = edge.first, v = edge.second;
    639             if (nxt[u] && nxt[u] != v) no(1);
    640             if (prv[v] && prv[v] != u) no(1);
    641             nxt[u] = v;
    642             prv[v] = u;
    643         }
    644         ///check case 2
    645         for (auto u: adj[i]) if (!seen[u]) {
    646             seen[u] = 1;
    647             int cur = nxt[u];
    648             while (cur) {
    649                 if (cur == u) no(2);
    650                 if (seen[cur]) break;
    651                 seen[cur] = 1;
    652                 cur = nxt[cur];
    653             }
    654         }
    655         ///check case 3
    656         if (nxt[n+1]) {
    657             int cur = n + 1, all = 1;
    658             while (cur) {
    659                 if (cur == n + 2) break;
    660                 ++all;
    661                 cur = nxt[cur];
    662             }
    663             if (cur == n + 2 && all < adj[i].size()) no(3);
    664         }
    665         ///all good - for now
    666         int free = 0;
    667         for (auto u: adj[i]) if (u <= n && !prv[u]) ///fake edges doesn't count
    668             ++free;
    669         if (prv[n+2]) --free; ///connected to last edge => not free
    670         for (int j = 1; j <= free; ++j) ans = 1ll * ans * j % mod;
    671         ///reset
    672         for (auto u: adj[i]) nxt[u] = prv[u] = seen[u] = 0;
    673     }
    674 
    675     ///no conflicts
    676     cout << ans << endl;
    677     return 0;
    678 }
    679 ```