Recently I have been facing pinched nerve problems. I feel my right hand has got weaker . I am having thoughts that I maynot survive long on this planet . Pray for my recovery . In my little life codeforces has given me something to feel worthy of. I wanna thank the community for everything . And at last I seek everyone's prayer . It has been a journey to be cherished , I feel codeforces as my family , that's why I have shared my feelings here , Please pray for my recovery . I am only 22 and I wanna live and give some more contests.

Hii Codeforces!

We invite you to participate in CodeChef’s Starters 83, aka International Coding Marathon, in collaboration with Technex '23, IIT (BHU), this Wednesday, 29th March, rated for all divisions.

Time : 8:00 PM — 10:30 PM IST

Note that the duration is 2.5 hours. Read about the recent CodeChef changes here.

Joining us on the problem setting panel are

• Contest admin: Jatin rivalq Garg.
• Setters: Piyush piyush_pransukhka Pransukhka, Kushagra koderkushy Goel, Kartik Gokussjz Malik, Pranav pd_codes Dev, Jatin rivalq Garg, Devashish raideva Rai, Vansh vansh_s Sardana.
• Tester: Yash yash_daga Daga
• Statement Verifier: Kanhaiya notsoloud1 Mohan.
• Editorialist: Nishank IceKnight1093 Suresh.
• Video Editorialists: Madhav jhamadhav Jha, Suraj jhasuraj01 Jha, Jwala jwalapc

ICM is the flagship CP event of Byte the Bits, the set of programming events organized under Technex, the annual techno-management fest of the Indian Institute of Technology (BHU), Varanasi.

Prizes

Note: Prizes are only for Indian participants (combined ranklist for divisions 1 and 2).

• Winner: $$$10,000$$$ INR
• $$$1^{st}$$$ runner up: $$$6,000$$$ INR
• $$$2^{nd}$$$ runner up: $$$4,000$$$ INR
• Top $$$25$$$ contestants: Goodies and coupons

Please fill out this form to avail them.

Some of our previous rounds:

• ICM, Technex'20
• ICM, Technex'21
• ICM, Technex'22

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest.

The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

Thank you all for participating, I hope you enjoyed the problems! You can rate the problems of the round in the corresponding spoilers.

1798A - Showstopper

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    for i in range(n):
        if a[i] > b[i]:
            a[i], b[i] = b[i], a[i]
    if a[-1] == max(a) and b[-1] == max(b):
        print("YES")
    else:
        print("NO")

1798B - Three Sevens

MAX = 50000
last = [0] * (MAX + 777)
for _ in range(int(input())):
    m = int(input())
    a_ = []
    for day in range(m):
        n = int(input())
        a = list(map(int, input().split()))
        for x in a:
            last[x] = day
        a_.append(a)
    ans = [-1] * m
    for day in range(m):
        for x in a_[day]:
            if last[x] == day:
                ans[day] = x
        if ans[day] == -1:
            print(-1)
            break
    else:
        print(*ans)

1798C - Candy Store

from math import gcd
 
def lcm(a, b):
  return a * b // gcd(a, b)
 
for _ in range(int(input())):
    n = int(input())
    a = []
    b = []
    for i in range(n):
       ai, bi = map(int, input().split())
       a.append(ai)
       b.append(bi)
    g = 0
    l = 1
    ans = 1
    for i in range(n):
        g = gcd(g, a[i] * b[i])
        l = lcm(l, b[i])
        if g % l:
            ans += 1
            g = a[i] * b[i]
            l = b[i]
    print(ans)

1798D - Shocking Arrangement

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    if max(a) == 0:
        print("No")
    else:
        print("Yes")
        prefix_sum = 0
        pos = []
        neg = []
        for x in a:
            if x >= 0:
                pos.append(x)
            else:
                neg.append(x)
        ans = []
        for _ in range(n):
            if prefix_sum <= 0:
                ans.append(pos[-1])
                pos.pop()
            else:
                ans.append(neg[-1])
                neg.pop()
            prefix_sum += ans[-1]
        print(' '.join(list(map(str, ans))))

1798E - Multitest Generator

N = 300777
a = [0] * N
go = [0] * N
good_chain = [0] * N
chain_depth = [0] * N
suf_max_chain_depth = [0] * N

ans = ""
for _ in range(int(input())):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    chain_depth[n + 1] = 0
    suf_max_chain_depth[n + 1] = 0
    curr_max_chain_depth = 0
    for i in range(n, 0, -1):
        go[i] = i + a[i] + 1
        if go[i] == n + 1 or (go[i] <= n and good_chain[go[i]]):
            good_chain[i] = True
        else:
            good_chain[i] = False
        chain_depth[i] = 1 + chain_depth[min(go[i], n + 1)]
        suf_max_chain_depth[i] = 1 + curr_max_chain_depth
        if go[i] <= n + 1:
            suf_max_chain_depth[i] = max(suf_max_chain_depth[i], 1 + suf_max_chain_depth[go[i]])
        if good_chain[i]:
            curr_max_chain_depth = max(curr_max_chain_depth, chain_depth[i])
    for i in range(1, n):
        if good_chain[i + 1] and chain_depth[i + 1] == a[i]:
            ans += "0 "
        elif good_chain[i + 1] or suf_max_chain_depth[i + 1] >= a[i]:
            ans += "1 "
        else:
            ans += "2 "
    ans += '\n'
print(ans)

1798F - Gifts from Grandfather Ahmed

#include <bits/stdc++.h>
 
#define pb push_back
// #define int long long
#define all(x) x.begin(), x.end()
#define ld long double
using namespace std;
const int N = 210;
bool dp[N][N][N];
bool take[N][N][N];
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n), s(k);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < k; i++) {
        cin >> s[i];
    }
    vector<pair<int, int>> s2;
    for (int i = 0; i < k; i++) {
        s2.pb({s[i], i});
    }
    sort(all(s2));
    vector<vector<int>> ans(k);
    for (int i = 0; i < k - 1; i++) {
        int class_size = s2[i].first;
        vector<int> boxes;
        for (int _ = 0; _ < 2 * class_size - 1; _++) {
            boxes.pb(a.back());
            a.pop_back();
        }
        for (int sz = 0; sz <= class_size; sz++) {
            for (int r = 0; r < class_size; r++) {
                dp[0][sz][r] = false;
                take[0][sz][r] = false;
            }
        }
        dp[0][0][0] = true;
        dp[0][1][boxes[0] % class_size] = true;
        take[0][1][boxes[0] % class_size] = true;
        for (int j = 1; j < (int) boxes.size(); j++) {
            for (int sz = 0; sz <= class_size; sz++) {
                for (int r = 0; r < class_size; r++) {
                    dp[j][sz][r] = dp[j - 1][sz][r];
                    if (sz > 0 && dp[j - 1][sz - 1][(class_size + r - boxes[j] % class_size) % class_size]) {
                        dp[j][sz][r] = true;
                        take[j][sz][r] = true;
                    } else {
                        take[j][sz][r] = false;
                    }
                }
            }
        }
        vector<bool> used(2 * class_size - 1);
        int sz = class_size, r = 0;
        for (int j = (int) boxes.size() - 1; j >= 0; j--) {
            if (take[j][sz][r]) {
                used[j] = true;
                sz--;
                r += (class_size - boxes[j] % class_size);
                r %= class_size;
            } else {
                used[j] = false;
            }
        }
        vector<int> to_class;
        for (int j = 0; j < (int) boxes.size(); j++) {
            if (!used[j]) {
                a.pb(boxes[j]);
            } else {
                to_class.pb(boxes[j]);
            }
        }
        ans[s2[i].second] = to_class;
    }
 
    int sum = 0;
    for (auto x : a) {
        sum += x;
        sum %= (int) (a.size() + 1);
    }
    int add = (int) (a.size() + 1) - sum;
    ans[s2[k - 1].second] = a;
    ans[s2[k - 1].second].pb(add);
 
    cout << add << '\n';
    for (auto arr : ans) {
        for (auto x : arr) {
            cout << x << ' ';
        }
        cout << '\n';
    }
}

Hello Codeforces, I am a 15 year old high school student that works hard to improve, after reaching Cyan with 4 months of practice, going on for another 2 months without much improvement and a 2.5 month break, I have just reached Expert after around 9 months. I would like to learn what difficulty range I should study from and what resources would be most beneficial in your opinion. Thank you in advance.

Hello, Codeforces!

We are happy to invite you to TheForces Round #9 (Fool-Forces), which will take place on Mar/30/2023 18:05 (Moscow time)

Please don't forget the time, 30 March!

This competition is similar to April Fool's Day Contests, As there's an official round on April 1st this year, We decided to hold our round sooner.

You will have 2 hours to solve 8 problems.

• Problems were prepared and authored by Parisa_Amiri and E404_Not_Found.

• Would like to thank our testers: Little_Sheep_Yawn, wuhudsm, O--O, Nafis, sjNxksbzj, _Prince.

• Also we want to thank you for participating in our round.

P.S : The problems are not sorted by difficulty, So please do read all the problems, Also the round will be available in gym for everyone after the contest end!

P.S.2 : The top places will be published after the contest.

"Stay hungry! Stay foolish!" Steve Jobs.

Discord Group (500+ people)

Contests' archive

Hi all,

The final contest of the 2022-2023 USACO season will be running from March 24th to March 27th. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

For those unfamiliar with the USACO contest format, please refer to the contest instructions and rules. We provide a short FAQ but folks should read all the rules carefully.

I have a question about the contest. Where do I ask it?

Email the contest director via the instructions above. Do not post anything publicly about the questions (including but not limited to your scores, how you felt about the problems, any content of the problems, etc) until after the contest is over for everyone. Do not DM me or anyone else affiliated with USACO, only the contest director can assist you. The contest director does not monitor Codeforces, this blog post is merely a courtesy to inform other people of the contest.

When can I enter the contest?

The contest will open on March 24th.

If I submit multiple programs, which one gets evaluated?

Only the last submission will be evaluated for official scoring purposes.

Can I use prewritten code / templates?

No.

Am I allowed to use outside resources during the contest?

You may only refer to language documentation.

Why didn't I get an email from USACO when I registered my account?

Follow the directions on the USACO website regarding Gmail Delivery Issues to contact the contest director.

Can I solve problems in Rust?

No, the only languages supported are C, C++, Java, and Python. Consult the instructions for language-specific technical details.

Will Rust support be added?

Petition IOI to add Rust support first.

Nowcoder problem (Chinese) link. The submission is private because I don't want to publish my Nowcoder account, but you can copy the code at the end of this blog and paste it to the answer sheet, it will get AC.

English version

First I would like to thank ShaoNianTongXue5307 for his idea!

This is a learning note, most for myself. Most of this blog is not original.

Part 1: Problem Statement:

A tree $$$T=(V, E)$$$ has $$$n$$$ vertices and $$$n-1$$$ edges, the weight of each vertex $$$i$$$ is $$$a_i$$$.

For each edge $$$e$$$, you can determine its direction, i.e., for two vertices $$$u, v$$$, there are two states: $$$u \rightarrow v$$$ and $$$v \rightarrow u$$$. There are $$$2^{n-1}$$$ states in total.

For each state $$$S$$$, we define $$$f(S)$$$ as

$$$f(S) := \sum\limits_{(u, v) \in V \times V, v\,\text{is reachable from}\,u} |a_u - a_v|$$$.

Compute the sum of $$$f(S)$$$ over all $$$2^{n-1}$$$ states $$$S$$$, modulo $$$998244353$$$.

Example:

Suppose $$$n=3$$$, and two edges connect $$$(1, 2), (2, 3)$$$, respectively. $$$a_1 = 3, a_2 = 1, a_3 = 2$$$, the answer is $$$14$$$.

Constraints: $$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq a_i \leq 10^9$$$.

Part 2: What is the centroid decomposition good at?

Before we learn centroid decomposition, we should first know what it is good at. For a tree $$$T = (V, E)$$$, we can decompose $$$V$$$ into $$$V = V_1 \cup V_2 \cup ... \cup V_t$$$, where $$$V_i (1 \leq i \leq t)$$$ are pairwise disjoint non-empty sets. $$$V_1$$$ is a singleton which contains only one element: The centroid. $$$V_2, ..., V_t$$$ are the connected components of $$$T \setminus V_1$$$. We want to calculate some function $$$f(T)$$$, and we assume that the base case, where $$$V(T) = 1$$$, is easy to calculate. This assumption is not strict, because if we can't even deal with the case where $$$V(T)=1$$$, we can actually achieve nothing. The another important function besides $$$f$$$ is the merge function: $$$merge(V_1, V_2, ..., V_t)$$$. Formally

$$$f(V) = \sum\limits_{i=1}^t f(V_i) + merge(V_1, V_2, ..., V_t)$$$. (1)

Like the merge sort, the number of iterations in the centroid decomposition algorithm is $$$O(log |V|)$$$, so it takes roughly $$$O(log |V| \cdot merge)$$$ time. Therefore, the most important advantage to use centroid decomposition is that the merge function could be computed fast enough. Otherwise, it is even slower than the brute force! In our solution merge is $$$O(|V|log|V|)$$$ so its complexity is $$$O(|V|log^2|V|)$$$. You may recall the process of the merge sort if you have trouble understanding these words.

Part 3: What is a centroid, and what is a centroid decomposition?

For a tree, the vertex $$$v$$$ is called a centroid if and only if any subtree rooted at $$$v$$$'s child has a size at most half the size of the original tree. For example, the centroids for the path A--B--C--D are B and C.

Property $$$1$$$: A tree has one or two centroids.

Proof: First, we prove that one tree has at least one centroid. The centroid could be found using a constructive algorithm. First we specify an original root $$$r$$$. Initialize $$$v$$$ as $$$r$$$. Check whether $$$v$$$ is a centroid. If yes, we have already done. If not, replace $$$v$$$ with $$$v$$$'s heavy child $$$u$$$, i.e., $$$argmax(u)\{size[u] \mid u\,\text{is}\,v\text{'s child}\}$$$. The iteration will terminate since the size if finite. When it terminates, the size of subtrees rooted at $$$v$$$'s children $$$\leq \frac{|V|}{2}$$$. We need to be careful that, when the tree is rooted at $$$v$$$ (instead of $$$r$$$), the parent of $$$v$$$ in the $$$r$$$-rooted tree becomes a child of $$$v$$$ in the $$$v$$$-rooted tree, so we need to check the parent of $$$v$$$ in the $$$r$$$-rooted tree. Since the algorithm does not terminate at $$$v$$$'s parent, the size of $$$v \leq \frac{|V|}{2}$$$, therefore, (the size of $$$v$$$'s parent) — (the size of $$$v$$$) $$$\leq \frac{|V|}{2}$$$, which also satisfies the condition.

Second, we prove that one tree has at most two centroids. Suppose $$$a$$$ and $$$b$$$ are two centroids. Then, there is a subtree of $$$a$$$'s child ($$$A$$$) containing $$$b$$$, and a subtree of $$$b$$$'s child ($$$B$$$) containing $$$a$$$, $$$A \cup B = V, |A|, |B| \leq \frac{|V|}{2}$$$. By the principle of inclusion-exclusion (PIE), $$$A$$$ and $$$B$$$ must be disjoint, therefore there is an edge $$$ab$$$. So there cannot be $$$\geq 3$$$ centroids, and if it contains $$$2$$$ centroids, these two centroids must be adjacent.

Property $$$2$$$: $$$v := argmin(v)\{max\{size[u] \mid u\,\text{is}\,v\text{'s child in the tree rooted at }v\}\}$$$ is a centroid. This can be proved using the fact that every tree has at least one centroid, so the "best" vertex must be a centroid. In English, for a vertex $$$v$$$, lets the score of $$$v$$$ be the maximum size of subtrees rooted at $$$v$$$'s children in the $$$v$$$-rooted tree. The $$$v$$$ with the minimum score is the centroid.

For example, the edges are $$$(A, B), (B, D), (B, C), (C, E)$$$. The scores of $$$A,B,C,D,E$$$ are $$$4, 2, 3, 4, 4$$$ respectively, so the centroid is $$$B$$$.

Property $$$3$$$: $$$v$$$ is a centroid if and only if for arbitrary $$$q \in V$$$, $$$\sum\limits_{u \in V} d(u, v) \leq \sum\limits_{u \in V} d(u, q)$$$.

Proof: $$$\rightarrow$$$: $$$v$$$ is a centroid. Let's $$$qs$$$ be the size of subtree of $$$v$$$'s child that contains $$$q$$$. For the $$$qs2$$$ part (the subtree rooted at $$$q$$$), each vertex decreases $$$d(q, v)$$$, for the $$$|V|-qs$$$ part, each vertex increases $$$d(q, v)$$$, and for the $$$qs-qs2$$$ part, we don't know exactly, but each of vertex decreases at most $$$d(q, v)$$$ (if $$$qs > qs2$$$, the upper bound of total decrease $$$(qs-qs2)d(q, v)$$$ cannot be achieved), so the general distance sum increases when $$$v$$$ moves to $$$q$$$ as $$$qs \leq \frac{|V|}{2}$$$ by the definition of the centroid.

$$$\leftarrow$$$: If $$$qs > qs2$$$, then the $$$qs-qs2$$$ part decreases strictly less then $$$(qs-qs2) \cdot d(q, v)$$$, and the $$$qs$$$ part decreases strictly less then $$$qs \cdot d(q, v) \leq (|V| - qs) \cdot d(q, v)$$$. Therefore, $$$qs = qs2 = \frac{|V|}{2}$$$. There fore $$$q$$$ and $$$v$$$ are adjacent, the size of subtree rooted at $$$v$$$ in a $$$q$$$-rooted tree is $$$\frac{|V|}{2}$$$, therefore $$$q$$$ is a centroid.

Property $$$4$$$: Suppose $$$v$$$ is a centroid of the original tree $$$T$$$. If one leaf node is added to or deleted from $$$T$$$, then there is a centroid of $$$T$$$ (after operation) among $$$\{v\} \cup N(v)$$$, where $$$N(v)$$$ is the neighbor of $$$v$$$. Simply speaking, if $$$v$$$ is not a centroid after adding that leaf, we can replace $$$v$$$ with one of $$$v$$$'s child whose subtree contains that leaf. If $$$v$$$ is not a centroid after deleting that leaf, we can replace $$$v$$$ with $$$v$$$'s heavy child.

Counterexample $$$1$$$: The diameter may not pass the centroid.

Somebody thinks the diameter must pass the centroid. That is wrong! The diameter may not pass the centroid.

Centroid decomposition is a recursion process. Just find one centroid of the tree (if there are two centroid, find an arbitrary one of it), delete the centroid and the edges connecting to it. After that, the tree is decomposed into several connected components. Then, we do such decomposition for every connected component. Stop the recursion process if the vertex set of the tree is a singleton. Since each iteration halves the size, the centroid decomposition takes at most $$$O(log|V|)$$$ rounds.

Code: My code is adapted from this blog by lingfunny. It can AC ABC291EX Balanced Tree, submission is here. I paste the core code here:

struct cdt{
    const int cdtINF = 0x7fffffff;
    int *mxsz, *sz, *p, rt, nm;
    //sz(x): The size of x
    //mxsz(x): max{sz(y)|y is a child of x}
    //p parent
    bool* vis; //for convenience, we don't use a bitset here. But we can!
    std::vector<int>* g;
 
    cdt(int n):rt(0), nm(n){
        assert(n > 0);
        mxsz = new int[n+1];
        mxsz[0] = cdtINF;
        sz = new int[n+1];
        p = new int[n+1];
        g = new std::vector<int>[n+1];
        vis = new bool[n+1];
        memset(vis, 0, (n+1)*sizeof(bool));
    }
 
    ~cdt(){
        delete[] mxsz;
        delete[] sz;
        delete[] p;
        delete[] g;
        delete[] vis;
    }
 
    void addedge(int u, int v){
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    void calcsize(int u, int fa){
        mxsz[u] = sz[u] = 1;
        for(int v: g[u]){
            if(!vis[v] && v != fa){
                calcsize(v, u);
                sz[u] += sz[v];
                mxsz[u] = std::max(mxsz[u], sz[v]);
            }
        }
        mxsz[u] = std::max(mxsz[u], nm-sz[u]);
        //mxsz最小的一定是树的重心, 因为一棵树至少有一个重心, 可能有1个或2个重心
        //The argmin mxsz has to be the centroid, because one tree has at least one centroid!
        if(mxsz[u] <= mxsz[rt]) rt = u;
    }
 
    void operate(int u, int fa){
        calcsize(u, -1), calcsize(rt, -1), p[rt] = fa, dfz(rt);
    }
 
    void dfz(int u){
        vis[u] = 1;
        for(int v: g[u]){
            if(!vis[v]){
                nm = sz[v], rt = 0;
                operate(v, u);
            }
        }
    }
};

int main(void){
    int n;
    cin >> n;
    cdt c(n); 
    for(int i = 1, u, v; i <= n; ++i){
        cin >> u >> v;
        c.addedge(u, v);
    }
    c.operate(1, -1);
}

This code is a little bit comprehensive. It contains three recursions: operate, calcsize and dfz. It starts with operate, operate will call calcsize and dfz. calcsize will call itself and dfz will call operate in turn. The calcsize function is easier to understand, it has two usage: Calculate the size of each subtree, and find the centroid. Note that we call calcsize twice in the operation function, that is quite necessary: In the first call, we find the centroid, and in the second call, we find the size of each connected components. Then, the operation function calls the dfz function. In the initial call of dfz, i.e., the call from operation rather than the call from dfz itself, the parameter int u is guaranteed to be a centroid, so it recursively removes this centroid $$$V_1$$$ and decomposes $$$T \setminus V_1$$$ into connected components $$$V_2, V_3, ..., V_t$$$. The father (parent) of the centroids of $$$V_2$$$, $$$V_3$$$, ..., $$$V_t$$$ are all $$$V_1$$$, this is achieved using p[rt] = fa. There is no merge (described in the Part 2) operations in the code above. If there is a merge operation, we should place it at the end of the dfz function.

This is a graph from Xing-Ling's blog. $$$1$$$ is the centroid of the original tree. If we cut $$$1$$$, we get two connected components: $$$\{2,3,4,5,6\}$$$ and $$$\{7,8,9,10,11\}$$$. The centroids of these two connected components are $$$2$$$ and $$$7$$$ respectively, so the fathers (parents) of $$$2$$$ and $$$7$$$ are both $$$1$$$. Then we do the centroid decomposition in each component...

Part 4: Back to the original problem: How should we write the merge function?

This part is similar to the EATROCK from CodeChef Starter80A. The original Nowcoder problem is much harder than this CodeChef problem, only $$$8$$$ participants solve it.

In the merge function, we only consider $$$u$$$ and $$$v$$$ are from the different components in each iteration. In this case, $$$d(u, v) = dep(u) + dep(v)$$$, where $$$dep(\cdot)$$$ denotes the depth of $$$\cdot$$$ in the current tree. For $$$u$$$ and $$$v$$$ from different components, if $$$v$$$ is reachable from $$$u$$$, then $$$d(u, v) = dep(u) + dep(v)$$$ edges have to be fixed, so there are $$$n - dep(u) - dep(v) - 1$$$ free edges. So each $$$(u, v)$$$ pair appears $$$2^{n - dep(u) - dep(v) - 1}$$$ times, contributing $$$2^{n - dep(u) - dep(v) - 1}|a_u - a_v|$$$ to the final answer. The total contribution in each decomposition iteration is

$$$2^n \sum\limits_{a_v \leq a_u} (a_u - a_v)2^{-dep(u)-dep(v)} = 2^n (\sum\limits_{u} a_u2^{-dep(u)}(\sum\limits_{v, a_v \leq a_u}2^{-dep(v)}) - \sum\limits_{u}2^{-dep(u)}(\sum\limits_{v, a_v \leq a_u}a_v2^{-dep(v)}))$$$ (2).

Then, we can implement the merge by sorting $$$a$$$ and maintaining two prefix sums: $$$\sum\limits_{v} a_v2^{-dep(v)}$$$ and $$$\sum\limits_{v} 2^{-dep(v)}$$$. The complexity is $$$O(|V|log|V|)$$$ for each iteration because the sorting is a bottleneck. The overall complxity is $$$O(|V|log^2|V|)$$$ with a slightly larger constant, but the nowcoder machine is really fxxking fast. Code (645ms):

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")

//jiangly Codeforces
constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm((int)(x % P))) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

#define C 200005
int a[C];
Z finalans = 0;
Z p2[C], p2inv[C];
Z all1, all2;
std::vector<Z> curtag1(C), curtag2(C);

struct cdt{
    const int cdtINF = 0x7fffffff;
    int *mxsz, *sz, *p, rt, nm;
    //sz(x): The size of x
    //mxsz(x): max{sz(y)|y is a child of x}
    //p parent
    bool* vis; //for convenience, we don't use a bitset here. But we can!
    std::vector<int>* g;
    //aifrom = ai + from. 
    //element[0]: a[i].
    //element[1]: Which tree it belongs to.
    //element[2]: The depth, i.e., the distance between this element to the centroid

    cdt(int n):rt(0), nm(n){
        assert(n > 0);
        mxsz = new int[n+1];
        mxsz[0] = cdtINF;
        sz = new int[n+1];
        p = new int[n+1];
        g = new std::vector<int>[n+1];
        vis = new bool[n+1];
        memset(vis, 0, (n+1)*sizeof(bool));
    }

    ~cdt(){
        delete[] mxsz;
        delete[] sz;
        delete[] p;
        delete[] g;
        delete[] vis;
    }

    void addedge(int u, int v){
        g[u].push_back(v);
        g[v].push_back(u);
    }

    void calcsize(int u, int fa, int tag, int depth, std::vector<std::array<int, 4>>* aifrom){
        mxsz[u] = sz[u] = 1;
        if(aifrom){
            aifrom->push_back(std::array<int, 4>{a[u], tag, depth, u});
        }
        for(int v: g[u]){
            if(!vis[v] && v != fa){
                calcsize(v, u, tag, depth+1, aifrom);
                sz[u] += sz[v];
                mxsz[u] = std::max(mxsz[u], sz[v]);
            }
        }
        mxsz[u] = std::max(mxsz[u], nm-sz[u]);
        //mxsz最小的一定是树的重心, 因为一棵树至少有一个重心, 可能有1个或2个重心
        //The argmin mxsz has to be the centroid, because one tree has at least one centroid!
        if(mxsz[u] <= mxsz[rt]) rt = u;
    }

    void operate(int u, int fa, std::vector<std::array<int, 4>>* aifrom){
        //tag: Note which subtree, i.e., which connected component u belongs to after the centroid decomposition!
        calcsize(u, -1, u, 1, aifrom), calcsize(rt, -1, u, 1, nullptr), p[rt] = fa;
        dfz(rt);
    }

    void dfz(int u){
        vis[u] = 1;
        std::vector<std::array<int, 4>> aifrom;
        aifrom.push_back(std::array<int, 4>{a[u], 0, 0, u});
        for(int v: g[u]){
            if(!vis[v]){
                nm = sz[v], rt = 0;
                operate(v, u, &aifrom);
            }
        }
        std::sort(aifrom.begin(), aifrom.end());
        all1 = 0, all2 = 0;
        for(int i = 0; i < aifrom.size(); ++i){
            curtag1[aifrom[i][1]] = 0;
            curtag2[aifrom[i][1]] = 0;
        }
        Z tmp = 0; //The tmp in unnecessary. It helps me debug.
        for(int i = 0; i < aifrom.size(); ++i){
            int tag = aifrom[i][1];
            Z curcoeff1 = aifrom[i][0] * p2inv[aifrom[i][2]];
            tmp += curcoeff1 * (all1 - curtag1[tag]);
            Z curcoeff2 = p2inv[aifrom[i][2]];
            tmp -= curcoeff2 * (all2 - curtag2[tag]);
            all1 += curcoeff2;
            curtag1[tag] += curcoeff2;
            all2 += curcoeff1;
            curtag2[tag] += curcoeff1;
        }
        finalans += tmp;
    }
};

#define DEBUG 0
#define SINGLE 1
#define BT(x, i) (((x) & (1 << (i))) >> (i))
#define fastio std::cin.tie(0) -> sync_with_stdio(0) 

void debug(const char* p){
    #if DEBUG
    freopen(p, "r", stdin); 
    #else
    fastio;
    #endif      
}

void solve(int test){
    int n;
    std::cin >> n;
    p2[0] = 1, p2inv[0] = 1;
    cdt c(n);
    int b[C];
    for(int i = 1, u, v; i < n; ++i){
        std::cin >> u >> v;
        c.addedge(u, v); 
    }
    for(int i = 1; i <= n; ++i){
        std::cin >> a[i];
        b[i] = a[i];
        p2[i] = Z(2) * p2[i-1];
        p2inv[i] = p2[i].inv();
    }
    c.operate(1, -1, nullptr);
    finalans *= p2[n];
    std::cout << finalans.val() << "\n";
}

int main(int argc, char** argv){
    debug(argc==1?"test1.txt":argv[1]);
    int t = 1;
    int test = 1;
    #if !SINGLE
    std::cin >> t;
    #endif
    while(t--){
        solve(test++);
    }
}

Hello Codeforces!

We are excited to invite you to compete in the California Informatics Competition (CALICO) Spring '23! The contest will take place on Saturday, April 8, 2023 from 4:00 p.m. to 6:30 p.m. Pacific Time. Registrations are now open and will be until Thursday, April 6, 2023 at 11:59 p.m. Pacific Time, so register here while you can! The contest will take place virtually on our custom judge platform.

The California Informatics Competition (CALICO) is a semiannual team programming contest organized by students at the University of California, Berkeley. We create original problems to encourage students to grow their problem-solving skills and learn algorithms in fun and exciting ways. Check out our website to learn more about the contest and join our discord server to get announcements, make teams, hang out, and more!

The contest will be 2.5 hours long and you can compete solo or in a team of up to 3. There will be around 8 problems spanning a wide range of difficulty for all skill levels. Some problems will have bonus test sets, where more efficient or advanced solutions can earn additional points. At least one of the problems will be interactive. Anyone can compete in the contest, but only pre-college teams will be eligible to win prizes. Editorials for each problem will also be available after the contest. More details will be released as the contest date approaches.

These awesome problems and editorials are written, prepared, and tested by the CALICO Team, including Bungmint, plourde27, yjp20, TheKingAleks, ss1237, bradley.louie1, fatant, KradecaNaLukcheta, mudkip, alfphaderp, voidcs, vcivek, skywire2000, and many more!

We’ve had a ton of fun creating these problems! We think there will be something interesting for everyone, regardless if you’re totally new or an experienced competitor.

Good luck on the contest!

Link to English flyer | Chinese flyer

As a college student, I thought I would do problem-solving and learn development parallelly. But I have noticed when I get too much involved in problem-solving, I would try to avoid development. And similarly is the case when I do development for a couple of days, I would try to avoid problem-solving.

Greetings Codeforces,

Competitive Programming Club, AIT Pune is excited to invite you to CoDeft 3.0 which will take place on Monday, March 27, 2023, at 20:00 IST. This contest will be an ICPC-styled contest to provide an exciting learning platform to showcase your CP skills. Many thanks to all the individuals who made this contest possible:

• Problem Setters: (_AbRn_, RohitRKS)

• (novaa, shreyas__09_) for testing and providing detailed feedback that improved the quality and balance of the round significantly.

• (Dev_Manus, hugewarriors) for coordinating the event!

This event will be conducted in 2 stages:

Qualifiers

• Date & Time: Monday, March 27, 2023, at 20:00 IST

• Participation: Individual

• Contest Link: https://www.codechef.com/CDFT2023

• Registration Link: http://shorturl.at/frIMN

• The top 100 Participants willing to come for the onsite finals will qualify for the final round.

Finals

• Date: Friday, April 14, 2023

• Participation: Individual

• Mode: Onsite, the Top 100 participants from online qualifiers will be invited for onsite finals at AIT, Pune Campus.

• Participants reporting for onsite finals will have four events CodeRed, Bug-Off, Retracer, and Short-Code to take part in.

Onsite Final Events:

◉ Codered: Competitive Programming event

◉ Retracer: Figuring out the code using only the input and output files

◉ Bug-Off: Debug the Code

◉ Short-Code: Smaller Code Wins!!

Prizes and Goodies

Qualifiers

• The top 25 Indian participants will receive goodies, delivered to their addresses.

• 5 Random Indian participants from the top 300 will receive goodies, delivered to their addresses.

• 5 Random students from AIT will receive goodies.

Finals

• All the onsite finalists will receive a CoDeft T-shirt + Goodies

• Event Winner, Runner Up

• CodeRed: 12,000/- INR and 8,000/- INR

• Retracer: 6,000/- INR and 4,000/- INR

• Bug-Off: 6,000/- INR and 4,000/- INR

• Short-Code: 6,000/- INR and 4,000/- INR

• Goodies for the top 7 participants on the leaderboard for all three events separately.

Don't forget to register to be eligible for goodies and prizes — http://shorturl.at/frIMN

Join Discord Server for regular updates — https://discord.gg/dCSUUmRBBM