E. Anton and Tree

problem_index: E

time_limit: 3 seconds

memory_limit: 256 megabytes

solutions: ["def main():\n\tn = int(input())\n\tcolors = input()[::2]\n\tdsu = list(range(n))\n\tedges = [[] for _ in range(n)]\n\tfor _ in range(n - 1):\n\t\t(u, v) = list(map(int, input().split()))\n\t\tu -= 1\n\t\tv -= 1\n\t\tif colors[u] == colors[v]:\n\t\t\t(a, b) = (dsu[u], dsu[v])\n\t\t\twhile a != dsu[a]:\n\t\t\t\ta = dsu[a]\n\t\t\twhile b != dsu[b]:\n\t\t\t\tb = dsu[b]\n\t\t\tif a < b:\n\t\t\t\tdsu[b] = dsu[v] = a\n\t\t\telse:\n\t\t\t\tdsu[a] = dsu[u] = b\n\t\telse:\n\t\t\tedges[u].append(v)\n\tfor (u, v) in enumerate(dsu):\n\t\tdsu[u] = dsu[v]\n\td = {u: [] for (u, v) in enumerate(dsu) if u == v}\n\tfor (u, e) in enumerate(edges):\n\t\tfor v in e:\n\t\t\td[dsu[u]].append(dsu[v])\n\t\t\td[dsu[v]].append(dsu[u])\n\n\tdef bfs(x):\n\t\t(nxt, visited, t) = ([x], set(), 0)\n\t\twhile nxt:\n\t\t\tt += 1\n\t\t\t(cur, nxt) = (nxt, [])\n\t\t\tfor x in cur:\n\t\t\t\tvisited.add(x)\n\t\t\t\tfor y in d[x]:\n\t\t\t\t\tif y not in visited:\n\t\t\t\t\t\tnxt.append(y)\n\t\treturn (t, cur[0])\n\tprint(bfs(bfs(0)[1])[0] // 2)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "from collections import defaultdict, deque\n\nclass DSU:\n\n\tdef __init__(self, n):\n\t\tself.parents = [i for i in range(n)]\n\t\tself.ranks = [0 for i in range(n)]\n\n\tdef find_parent(self, v):\n\t\tif self.parents[v] == v:\n\t\t\treturn v\n\t\tself.parents[v] = self.find_parent(self.parents[v])\n\t\treturn self.parents[v]\n\n\tdef join_sets(self, u, v):\n\t\tu = self.find_parent(u)\n\t\tv = self.find_parent(v)\n\t\tif u != v:\n\t\t\tif self.ranks[u] < self.ranks[v]:\n\t\t\t\t(u, v) = (v, u)\n\t\t\tself.parents[v] = u\n\t\t\tif self.ranks[v] == self.ranks[u]:\n\t\t\t\tself.ranks[u] += 1\nn = int(input())\ndsu = DSU(n)\ncolors = list(map(int, input().split(' ')))\nvertices = []\nfor i in range(n - 1):\n\t(u, v) = [int(x) - 1 for x in input().split(' ')]\n\tif colors[u] == colors[v]:\n\t\tdsu.join_sets(u, v)\n\tvertices.append((u, v))\ngraph = defaultdict(list)\nfor (u, v) in vertices:\n\tif colors[u] != colors[v]:\n\t\tu = dsu.find_parent(u)\n\t\tv = dsu.find_parent(v)\n\t\tgraph[u].append(v)\n\t\tgraph[v].append(u)\n\ndef bfs(u):\n\td = dict()\n\td[u] = 0\n\tq = deque()\n\tq.append(u)\n\twhile q:\n\t\tu = q.pop()\n\t\tfor v in graph[u]:\n\t\t\tif v not in d:\n\t\t\t\td[v] = d[u] + 1\n\t\t\t\tq.append(v)\n\treturn d\nif graph:\n\tv = list(graph.keys())[0]\n\td = bfs(v)\n\tu = v\n\tfor i in d:\n\t\tif d[i] > d[u]:\n\t\t\tu = i\n\td = bfs(u)\n\tw = u\n\tfor i in d:\n\t\tif d[i] > d[w]:\n\t\t\tw = i\n\tprint((d[w] + 1) // 2)\nelse:\n\tprint(0)\n", "f = lambda : map(int, input().split())\n(s, n) = (0, int(input()))\ng = [set() for i in range(n + 1)]\nc = [0] + list(f())\nd = [0] * (n + 1)\nfor j in range(n - 1):\n\t(a, b) = f()\n\tg[a].add(b)\n\tg[b].add(a)\np = [q for (q, t) in enumerate(g) if len(t) == 1]\nwhile p:\n\ta = p.pop()\n\tif not g[a]:\n\t\tbreak\n\tb = g[a].pop()\n\tg[b].remove(a)\n\tif c[a] - c[b]:\n\t\td[a] += 1\n\ts = max(s, d[b] + d[a])\n\td[b] = max(d[b], d[a])\n\tif len(g[b]) == 1:\n\t\tp.append(b)\nprint(s + 1 >> 1)\n", "def main():\n\tfrom collections import defaultdict\n\t(n, colors) = (int(input()), input()[::2])\n\t(dsu, edges, d) = (list(range(n)), [], defaultdict(list))\n\tfor _ in range(n - 1):\n\t\t(u, v) = list(map(int, input().split()))\n\t\tu -= 1\n\t\tv -= 1\n\t\tif colors[u] == colors[v]:\n\t\t\t(a, b) = (dsu[u], dsu[v])\n\t\t\twhile a != dsu[a]:\n\t\t\t\ta = dsu[a]\n\t\t\twhile b != dsu[b]:\n\t\t\t\tb = dsu[b]\n\t\t\tif a < b:\n\t\t\t\tdsu[b] = dsu[v] = a\n\t\t\telse:\n\t\t\t\tdsu[a] = dsu[u] = b\n\t\telse:\n\t\t\tedges.append(u)\n\t\t\tedges.append(v)\n\tfor (u, v) in enumerate(dsu):\n\t\tdsu[u] = dsu[v]\n\twhile edges:\n\t\t(u, v) = (dsu[edges.pop()], dsu[edges.pop()])\n\t\td[u].append(v)\n\t\td[v].append(u)\n\n\tdef bfs(x):\n\t\t(nxt, avail, t) = ([x], [True] * n, 0)\n\t\twhile nxt:\n\t\t\tt += 1\n\t\t\t(cur, nxt) = (nxt, [])\n\t\t\tfor y in cur:\n\t\t\t\tavail[y] = False\n\t\t\t\tfor y in d[y]:\n\t\t\t\t\tif avail[y]:\n\t\t\t\t\t\tnxt.append(y)\n\t\treturn t if x else cur[0]\n\tprint(bfs(bfs(0)) // 2)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "import sys\nfrom collections import defaultdict, deque\n\ndef buildTree(root):\n\tq = deque()\n\tq.append((root, root))\n\tvis = [0 for _ in range(n + 1)]\n\tvis[root] = 1\n\twhile q:\n\t\t(v, fa) = q.pop()\n\t\tfor x in preedge[v]:\n\t\t\tif vis[x] != 1:\n\t\t\t\tvis[x] = 1\n\t\t\t\tif col[x] == col[fa]:\n\t\t\t\t\tq.append((x, fa))\n\t\t\t\telse:\n\t\t\t\t\tedge[fa].append(x)\n\t\t\t\t\tedge[x].append(fa)\n\t\t\t\t\tq.append((x, x))\n\ndef getDeep(root):\n\tvis = [0 for _ in range(n + 1)]\n\td = {}\n\tq = deque()\n\tq.append(root)\n\tvis[root] = 1\n\td[root] = 0\n\twhile q:\n\t\tu = q.pop()\n\t\tfor x in edge[u]:\n\t\t\tif vis[x] == 0:\n\t\t\t\tvis[x] = 1\n\t\t\t\td[x] = d[u] + 1\n\t\t\t\tq.append(x)\n\treturn d\nn = int(input())\nprecol = [int(_) for _ in input().split()]\npreedge = [[] for _ in range(n + 1)]\nfor _ in range(n - 1):\n\t(x, y) = [int(_) for _ in input().split()]\n\tpreedge[x].append(y)\n\tpreedge[y].append(x)\nroot = (n + 1) // 2\nedge = [[] for _ in range(n + 1)]\ncol = [0 for _ in range(n + 1)]\nfor x in range(1, n + 1):\n\tcol[x] = precol[x - 1]\nbuildTree(root)\nd = getDeep(root)\nu = max(d.keys(), key=lambda k: d[k])\nprint((max(getDeep(u).values()) + 1) // 2)\n"]

difficulty: HARD

source: codeforces

raw_problem:
E. Anton and Tree

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Anton is growing a tree in his garden. In case you forgot, the tree is a connected acyclic undirected graph.

There are n vertices in the tree, each of them is painted black or white. Anton doesn't like multicolored trees, so he wants to change the tree such that all vertices have the same color (black or white).

To change the colors Anton can use only operations of one type. We denote it as paint(v), where v is some vertex of the tree. This operation changes the color of all vertices u such that all vertices on the shortest path from v to u have the same color (including v and u). For example, consider the tree

and apply operation paint(3) to get the following:

Anton is interested in the minimum number of operation he needs to perform in order to make the colors of all vertices equal.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of vertices in the tree.

The second line contains n integers colori (0 ≤ colori ≤ 1) — colors of the vertices. colori = 0 means that the i-th vertex is initially painted white, while colori = 1 means it's initially painted black.

Then follow n - 1 line, each of them contains a pair of integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — indices of vertices connected by the corresponding edge. It's guaranteed that all pairs (ui, vi) are distinct, i.e. there are no multiple edges.

Output

Print one integer — the minimum number of operations Anton has to apply in order to make all vertices of the tree black or all vertices of the tree white.

Examples

Input

11
0 0 0 1 1 0 1 0 0 1 1
1 2
1 3
2 4
2 5
5 6
5 7
3 8
3 9
3 10
9 11

Output

2

Input

4
0 0 0 0
1 2
2 3
3 4

Output

0

Note

In the first sample, the tree is the same as on the picture. If we first apply operation paint(3) and then apply paint(6), the tree will become completely black, so the answer is 2.

In the second sample, the tree is already white, so there is no need to apply any operations and the answer is 0.

question:
Anton is growing a tree in his garden. In case you forgot, the tree is a connected acyclic undirected graph.
There are n vertices in the tree, each of them is painted black or white. Anton doesn't like multicolored trees, so he wants to change the tree such that all vertices have the same color (black or white).
To change the colors Anton can use only operations of one type. We denote it as paint(v), where v is some vertex of the tree. This operation changes the color of all vertices u such that all vertices on the shortest path from v to u have the same color (including v and u). For example, consider the tree
 ![image](1.png) and apply operation paint(3) to get the following:
 ![image](2.png) Anton is interested in the minimum number of operation he needs to perform in order to make the colors of all vertices equal.

Input
The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of vertices in the tree.
The second line contains n integers color_{i} (0 ≤ color_{i} ≤ 1) — colors of the vertices. color_{i} = 0 means that the i-th vertex is initially painted white, while color_{i} = 1 means it's initially painted black.
Then follow n - 1 line, each of them contains a pair of integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — indices of vertices connected by the corresponding edge. It's guaranteed that all pairs (u_{i}, v_{i}) are distinct, i.e. there are no multiple edges.

Output
Print one integer — the minimum number of operations Anton has to apply in order to make all vertices of the tree black or all vertices of the tree white.

Examples
Input
11
0 0 0 1 1 0 1 0 0 1 1
1 2
1 3
2 4
2 5
5 6
5 7
3 8
3 9
3 10
9 11

Output
2

Input
4
0 0 0 0
1 2
2 3
3 4

Output
0

Note
In the first sample, the tree is the same as on the picture. If we first apply operation paint(3) and then apply paint(6), the tree will become completely black, so the answer is 2.
In the second sample, the tree is already white, so there is no need to apply any operations and the answer is 0.

tags: ['Tree algorithms', 'Dynamic programming', 'Graph traversal']

skill_types: ['Dynamic programming']

image_tags: Tree Tree

data_split: test


E. Koxia and Tree

problem_index: E

time_limit: 3 seconds

memory_limit: 256 megabytes

note:
In the first test case, the tree is shown below. Vertices containing butterflies are noted as bold.
![image](images/cf_1770_E/1.png)
There are only $$$2$$$ butterflies so the choice of butterflies is fixed. Let's consider the following $$$4$$$ cases:
Edges are $$$1 \rightarrow 2$$$ and $$$2 \rightarrow 3$$$: butterfly on vertex $$$1$$$ moves to vertex $$$2$$$, but butterfly on vertex $$$3$$$ doesn't move. The distance between vertices $$$2$$$ and $$$3$$$ is $$$1$$$.  Edges are $$$1 \rightarrow 2$$$ and $$$3 \rightarrow 2$$$: butterfly on vertex $$$1$$$ moves to vertex $$$2$$$, but butterfly on vertex $$$3$$$ can't move to vertex $$$2$$$ because it's occupied. The distance between vertices $$$2$$$ and $$$3$$$ is $$$1$$$.  Edges are $$$2 \rightarrow 1$$$ and $$$2 \rightarrow 3$$$: butterflies on both vertex $$$1$$$ and vertex $$$3$$$ don't move. The distance between vertices $$$1$$$ and $$$3$$$ is $$$2$$$.  Edges are $$$2 \rightarrow 1$$$ and $$$3 \rightarrow 2$$$: butterfly on vertex $$$1$$$ doesn't move, but butterfly on vertex $$$3$$$ move to vertex $$$2$$$. The distance between vertices $$$1$$$ and $$$2$$$ is $$$1$$$.
Therefore, the expected value of Koxia's score is $$$\frac {1+1+2+1} {4} = \frac {5} {4}$$$, which is $$$748\,683\,266$$$ after modulo $$$998\,244\,353$$$.
In the second test case, the tree is shown below. Vertices containing butterflies are noted as bold. The expected value of Koxia's score is $$$\frac {11} {6}$$$, which is $$$831\,870\,296$$$ after modulo $$$998\,244\,353$$$.
![image](images/cf_1770_E/2.png)

solutions: ["import io,os\nfrom collections import deque \ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n\n\nM = 998244353\n\n\ndef fastfrac(a,b):\n    numb = pow(b,M-2,M)\n    return ((a%M)*(numb%M))%M\n\n\ndef main(t):\n\n\n    n,k = map(int,input().split())\n    points = list(map(int,input().split()))\n    for i in range(k):  points[i] -= 1\n    points = set(points)\n\n\n\n\n    neigh = [[] for _ in range(n)]\n    edges = []\n\n    for _ in range(n-1):\n        u,v = map(int,input().split())\n        neigh[u-1].append(v-1)\n        neigh[v-1].append(u-1)\n        edges.append((u-1,v-1))\n\n\n    subnum = [0]*n\n    subtot = [0]*n\n    subroot = [0]*n\n    parent = [-2]*n\n    queue = deque()\n    queue.append(0)\n    parent[0] = -1\n    children = [[] for _ in range(n)]\n    seq = []\n\n\n    while queue:\n        index = queue.popleft()\n        seq.append(index)\n        for nextindex in neigh[index]:\n            if parent[nextindex] > -2:  continue \n            parent[nextindex] = index\n            children[index].append(nextindex)\n            queue.append(nextindex)\n\n\n    for index in seq[::-1]:\n        if index in points:  subnum[index] += 1\n        for nextindex in neigh[index]:\n            subtot[index] += subtot[nextindex] + subnum[nextindex]\n            subnum[index] += subnum[nextindex]\n\n  \n \n    subroot[0] = subtot[0]\n    for index in seq[1:]:\n        subroot[index] = subroot[parent[index]] - subnum[index] + (k-subnum[index])\n\n\n    prob = [0]*n\n    invkk = fastfrac(1,k*k-k)\n    inv2 = fastfrac(1,2)\n\n\n    ans = 0\n    for index in range(n):\n        if index in points:\n            prob[index] = 1  \n            ans += subroot[index]\n            ans %= M\n\n##    print(subtot)\n#    print(subroot)\n    ans = (ans * invkk)%M\n\n#    print(ans)\n#    print(fastfrac(-1,2),\"should\")\n\n    for (u,v) in edges:\n        pu,pv = prob[u],prob[v]\n        uv = (pu * (1-pv) * inv2)%M\n        vu = (pv * (1-pu) * inv2)%M\n        prob[u] = (pu * pv + uv + vu)%M\n        prob[v] = prob[u]\n\n#        print(prob,sum(prob)%M,subnum[v])\n        if parent[u]==v:  \n            u,v = v,u\n            uv,vu = vu,uv\n\n        \n        ans += uv * (k - subnum[v] - 1 - subnum[v] ) * 2 * invkk % M\n        ans += vu * (subnum[v] - 1 - k + subnum[v] ) * 2 * invkk % M\n        ans %= M\n#        print(uv,vu,ans)        \n\n    print(ans)\n        \n\n        \n         \n \n\n\n        \n    \n\n \n\n\n    \n\n    \n\n\n           \n            \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nT = 1 #int(input())\nt = 1\nwhile t<=T:\n    main(t)\n    t += 1", "import sys\r\nfrom sys import stdin\r\n\r\nfrom collections import deque\r\ndef NC_Dij(lis,start):\r\n\r\n    ret = [float(\"inf\")] * len(lis)\r\n    ret[start] = 0\r\n    \r\n    q = deque([start])\r\n    plis = [i for i in range(len(lis))]\r\n    visit = []\r\n\r\n    while len(q) > 0:\r\n        now = q.popleft()\r\n        visit.append(now)\r\n\r\n        for nex in lis[now]:\r\n\r\n            if ret[nex] > ret[now] + 1:\r\n                ret[nex] = ret[now] + 1\r\n                plis[nex] = now\r\n                q.append(nex)\r\n\r\n    return ret,plis,visit\r\n\r\ndef inverse(a,mod):\r\n    return pow(a,mod-2,mod)\r\n\r\nmod = 998244353\r\nhalf = inverse(2,mod)\r\n\r\nuv = []\r\n\r\nn,k = map(int,stdin.readline().split())\r\n\r\na = list(map(int,stdin.readline().split()))\r\n\r\nlis = [[] for i in range(n)]\r\nfor i in range(n-1):\r\n    u,v = map(int,stdin.readline().split())\r\n    u -= 1\r\n    v -= 1\r\n    lis[u].append(v)\r\n    lis[v].append(u)\r\n\r\n    uv.append( (u,v) )\r\n\r\ndlis,plis,visit = NC_Dij(lis,0)\r\na_under = [0] * n\r\ndp = [0] * n\r\n\r\nfor i in range(k):\r\n    a[i] -= 1\r\n    a_under[a[i]] += 1\r\n    dp[a[i]] += 1\r\n\r\nvisit.reverse()\r\n\r\nfor v in visit:\r\n    if v != 0:\r\n        a_under[plis[v]] += a_under[v]\r\n\r\nans_original = 0\r\nfor i in range(1,n):\r\n    ans_original += (k-a_under[i]) * a_under[i]\r\n    ans_original %= mod\r\n\r\n#print (ans_original)\r\n\r\nans = ans_original\r\n\r\nfor u,v in uv:\r\n\r\n    if plis[u] != v:\r\n        u,v = v,u\r\n\r\n    assert plis[u] == v\r\n\r\n    newv = 0\r\n    newu = 0\r\n\r\n    u_to_v = (1 - dp[v]) * dp[u] * half % mod\r\n    v_to_u = (1 - dp[u]) * dp[v] * half % mod\r\n\r\n    sizeU = a_under[u]\r\n    sizeV = k - a_under[u]\r\n\r\n    #print (sizeU,sizeV)\r\n    #print (u+1,\"->\",v+1,\" :\", u_to_v , (sizeU-1 - sizeV) , \" \" , v_to_u , (sizeV-1 - sizeU) )\r\n    ans += (sizeU-1 - sizeV) * u_to_v\r\n    ans += (sizeV-1 - sizeU) * v_to_u\r\n    ans %= mod\r\n\r\n    # u -> v\r\n    newv += ( (1 - dp[v]) * dp[u] + dp[v]) * half\r\n    newu += dp[u] * dp[v] * half\r\n\r\n    # v -> u\r\n    newv += dp[u] * dp[v] * half\r\n    newu += ( (1 - dp[u]) * dp[v] + dp[u] ) * half\r\n\r\n    dp[u] = newu % mod\r\n    dp[v] = newv % mod\r\n\r\n    #print (dp)\r\n\r\nans *= inverse(k * (k-1) //2 , mod)\r\n\r\nprint (ans % mod)", "import io,os\nfrom collections import deque \ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n\n\nM = 998244353\n\n\ndef fastfrac(a,b):\n    numb = pow(b,M-2,M)\n    return ((a%M)*(numb%M))%M\n\n\ndef main(t):\n\n\n    n,k = map(int,input().split())\n    points = list(map(int,input().split()))\n    for i in range(k):  points[i] -= 1\n    points = set(points)\n\n\n\n\n    neigh = [[] for _ in range(n)]\n    edges = []\n\n    for _ in range(n-1):\n        u,v = map(int,input().split())\n        neigh[u-1].append(v-1)\n        neigh[v-1].append(u-1)\n        edges.append((u-1,v-1))\n\n\n    subnum = [0]*n\n    subtot = [0]*n\n    subroot = [0]*n\n    parent = [-2]*n\n    queue = deque()\n    queue.append(0)\n    parent[0] = -1\n    children = [[] for _ in range(n)]\n    seq = []\n\n\n    while queue:\n        index = queue.popleft()\n        seq.append(index)\n        for nextindex in neigh[index]:\n            if parent[nextindex] > -2:  continue \n            parent[nextindex] = index\n            children[index].append(nextindex)\n            queue.append(nextindex)\n\n\n    for index in seq[::-1]:\n        if index in points:  subnum[index] += 1\n        for nextindex in neigh[index]:\n            subtot[index] += subtot[nextindex] + subnum[nextindex]\n            subnum[index] += subnum[nextindex]\n\n  \n \n    subroot[0] = subtot[0]\n    for index in seq[1:]:\n        subroot[index] = subroot[parent[index]] - subnum[index] + (k-subnum[index])\n\n\n    prob = [0]*n\n    invkk = fastfrac(1,k*k-k)\n    inv2 = fastfrac(1,2)\n\n\n    ans = 0\n    for index in range(n):\n        if index in points:\n            prob[index] = 1  \n            ans += subroot[index]\n            ans %= M\n\n##    print(subtot)\n#    print(subroot)\n    ans = (ans * invkk)%M\n\n#    print(ans)\n#    print(fastfrac(-1,2),\"should\")\n\n    for (u,v) in edges:\n        pu,pv = prob[u],prob[v]\n        uv = (pu * (1-pv) * inv2)%M\n        vu = (pv * (1-pu) * inv2)%M\n        prob[u] = (pu * pv + uv + vu)%M\n        prob[v] = prob[u]\n\n#        print(prob,sum(prob)%M,subnum[v])\n        if parent[u]==v:  \n            u,v = v,u\n            uv,vu = vu,uv\n\n        \n        ans += uv * (k - subnum[v] - 1 - subnum[v] ) * 2 * invkk % M\n        ans += vu * (subnum[v] - 1 - k + subnum[v] ) * 2 * invkk % M\n        ans %= M\n#        print(uv,vu,ans)        \n\n    print(ans)\n        \n\n        \n         \n \n\n\n        \n    \n\n \n\n\n    \n\n    \n\n\n           \n            \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nT = 1 #int(input())\nt = 1\nwhile t<=T:\n    main(t)\n    t += 1", "import os, sys\r\nfrom io import BytesIO, IOBase\r\nfrom array import array\r\nfrom itertools import accumulate\r\nimport bisect\r\nimport math\r\nfrom collections import deque\r\n\r\n# from functools import cache\r\n# cache cf\u9700\u8981\u81ea\u5df1\u63d0\u4ea4 pypy3.9!\r\nfrom copy import deepcopy\r\n\r\n\r\nclass FastIO(IOBase):\r\n    newlines = 0\r\n\r\n    def __init__(self, file):\r\n        self._fd = file.fileno()\r\n        self.buffer = BytesIO()\r\n        self.writable = \"x\" in file.mode or \"r\" not in file.mode\r\n        self.write = self.buffer.write if self.writable else None\r\n\r\n    def read(self):\r\n        while True:\r\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))\r\n            if not b:\r\n                break\r\n            ptr = self.buffer.tell()\r\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n        self.newlines = 0\r\n        return self.buffer.read()\r\n\r\n    def readline(self):\r\n        while self.newlines == 0:\r\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))\r\n            self.newlines = b.count(b\"\\n\") + (not b)\r\n            ptr = self.buffer.tell()\r\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n        self.newlines -= 1\r\n        return self.buffer.readline()\r\n\r\n    def flush(self):\r\n        if self.writable:\r\n            os.write(self._fd, self.buffer.getvalue())\r\n            self.buffer.truncate(0), self.buffer.seek(0)\r\n\r\n\r\nclass IOWrapper(IOBase):\r\n    def __init__(self, file):\r\n        self.buffer = FastIO(file)\r\n        self.flush = self.buffer.flush\r\n        self.writable = self.buffer.writable\r\n        self.write = lambda s: self.buffer.write(s.encode(\"ascii\"))\r\n        self.read = lambda: self.buffer.read().decode(\"ascii\")\r\n        self.readline = lambda: self.buffer.readline().decode(\"ascii\")\r\n\r\n\r\nsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\r\n\r\ninput = lambda: sys.stdin.readline().strip()\r\nints = lambda: list(map(int, input().split()))\r\nInt = lambda: int(input())\r\n\r\n\r\ndef queryInteractive(a, b, c):\r\n    print('? {} {} {}'.format(a, b, c))\r\n    sys.stdout.flush()\r\n    return int(input())\r\n\r\n\r\ndef answerInteractive(x1, x2):\r\n    print('! {} {}'.format(x1, x2))\r\n    sys.stdout.flush()\r\n\r\n\r\ninf = float('inf')\r\n\r\n\r\nn,k = ints()\r\np = [0]*n\r\na = ints()\r\nfor x in a:\r\n    p[x-1] = 1\r\n\r\ng = [[] for _ in range(n)]\r\ne = []\r\nfor _ in range(n-1):\r\n    u,v = ints()\r\n    u -= 1\r\n    v -= 1\r\n    g[u].append(v)\r\n    g[v].append(u)\r\n    e.append((u,v))\r\n\r\n\r\nMOD = 998244353\r\ndef exgcd(a, b):\r\n    if b == 0:\r\n        return 1, 0, a\r\n    else:\r\n        x, y, q = exgcd(b, a % b)\r\n        x, y = y, (x - (a // b) * y)\r\n        return x, y, q\r\n\r\n\r\ndef ModReverse(a, p):\r\n    x, y, q = exgcd(a, p)\r\n    return x % p\r\n\r\nsize = [0]*n\r\nfa = [-1]*n\r\n\r\n\r\nfrom types import GeneratorType\r\ndef bootstrap(f, stack=[]):\r\n    def wrappedfunc(*args, **kwargs):\r\n        if stack:\r\n            return f(*args, **kwargs)\r\n        else:\r\n            to = f(*args, **kwargs)\r\n            while True:\r\n                if type(to) is GeneratorType:\r\n                    stack.append(to)\r\n                    to = next(to)\r\n                else:\r\n                    stack.pop()\r\n                    if not stack:\r\n                        break\r\n                    to = stack[-1].send(to)\r\n            return to\r\n\r\n    return wrappedfunc\r\n\r\n@bootstrap\r\ndef dfs(x,f):\r\n    fa[x] = f\r\n    size[x] += p[x]\r\n    for y in g[x]:\r\n        if y == f:\r\n            continue\r\n        yield dfs(y,x)\r\n        size[x] += size[y]\r\n    yield\r\n\r\ninv2 = ModReverse(2,MOD)\r\ndfs(0,-1)\r\n\r\nans = 0\r\nfor i in range(n-1):\r\n    u,v = e[i]\r\n    if fa[u] == v:\r\n        u,v = v,u\r\n    \r\n    puv = (p[u]*(1-p[v]))%MOD\r\n    pvu = (p[v]*(1-p[u]))%MOD\r\n    delta = 0\r\n    delta -= (puv*size[v]*(k-size[v]))%MOD\r\n    delta -= (pvu*size[v]*(k-size[v]))%MOD\r\n    delta += (puv*(size[v] + 1)*(k-size[v] - 1))%MOD\r\n    delta += (pvu*(size[v] - 1)*(k-size[v] + 1))%MOD\r\n    ans += size[v]*(k-size[v]) + delta*inv2\r\n    ans = ans%MOD\r\n    p[u],p[v] = ((p[u]+p[v])*inv2)%MOD,((p[u]+p[v])*inv2)%MOD\r\n\r\nprint(ans*ModReverse( k*(k-1),MOD)*2%MOD)", "f=lambda:map(int,input().split())\r\nn,k=f()\r\nB=list(f())\r\nE=[list(f()) for _ in range(n-1)]\r\ng=[[] for _ in range(n+1)]\r\nfor a,b in E:\r\n    g[a].append(b)\r\n    g[b].append(a)\r\nS=[0]*(n+1)\r\nI=[0]*(n+1)\r\np=[0]*(n+1)\r\nfor e in B:p[e]=1\r\ndef F(u,f):\r\n    S[u]+=p[u]\r\n    for v in g[u]:\r\n        if(v==f):continue\r\n        F(v,u)\r\n        S[u]+=S[v]\r\n        I[v]=u\r\nF(1,0)\r\nR=0\r\nM=998244353\r\nJ=pow(2,M-2,M)\r\nL=pow(2,n,M)\r\nfor u,v in E:\r\n    if(I[v]==u):u,v=v,u\r\n    x=S[u]\r\n    R+=L*(x*(k-x)+J*(p[u]*(1-p[v])*(2*x-k-1)+p[v]*(1-p[u])*(k-2*x-1)))\r\n    R%=M\r\n    p[u]=p[v]=(p[u]+p[v])*J%M\r\nR*=pow(k*(k-1)//2*L,M-2,M)\r\nprint(R%M)"]

source: codeforces

raw_problem:
E. Koxia and Tree

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Imi has an undirected tree with $$$n$$$ vertices where edges are numbered from $$$1$$$ to $$$n-1$$$. The $$$i$$$-th edge connects vertices $$$u_i$$$ and $$$v_i$$$. There are also $$$k$$$ butterflies on the tree. Initially, the $$$i$$$-th butterfly is on vertex $$$a_i$$$. All values of $$$a$$$ are pairwise distinct.

Koxia plays a game as follows:

 For $$$i = 1, 2, \dots, n - 1$$$, Koxia set the direction of the $$$i$$$-th edge as $$$u_i \rightarrow v_i$$$ or $$$v_i \rightarrow u_i$$$ with equal probability.

 For $$$i = 1, 2, \dots, n - 1$$$, if a butterfly is on the initial vertex of $$$i$$$-th edge and there is no butterfly on the terminal vertex, then this butterfly flies to the terminal vertex. Note that operations are sequentially in order of $$$1, 2, \dots, n - 1$$$ instead of simultaneously.

 Koxia chooses two butterflies from the $$$k$$$ butterflies with equal probability from all possible $$$\frac{k(k-1)}{2}$$$ ways to select two butterflies, then she takes the distance$$$^\dagger$$$ between the two chosen vertices as her score.

Now, Koxia wants you to find the expected value of her score, modulo $$$998\,244\,353^\ddagger$$$.

$$$^\dagger$$$ The distance between two vertices on a tree is the number of edges on the (unique) simple path between them.

$$$^\ddagger$$$ Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input

The first line contains two integers $$$n$$$, $$$k$$$ ($$$2 \leq k \leq n \leq 3 \cdot {10}^5$$$) — the size of the tree and the number of butterflies.

The second line contains $$$k$$$ integers $$$a_1, a_2, \dots, a_k$$$ ($$$1 \leq a_i \leq n$$$) — the initial position of butterflies. It's guaranteed that all positions are distinct.

The $$$i$$$-th line in following $$$n − 1$$$ lines contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$) — the vertices the $$$i$$$-th edge connects.

It is guaranteed that the given edges form a tree.

Output

Output a single integer — the expected value of Koxia's score, modulo $$$998\,244\,353$$$.

Examples

Input

3 2
1 3
1 2
2 3

Output

748683266

Input

5 3
3 4 5
1 2
1 3
2 4
2 5

Output

831870296

Note

In the first test case, the tree is shown below. Vertices containing butterflies are noted as bold.

There are only $$$2$$$ butterflies so the choice of butterflies is fixed. Let's consider the following $$$4$$$ cases:

 Edges are $$$1 \rightarrow 2$$$ and $$$2 \rightarrow 3$$$: butterfly on vertex $$$1$$$ moves to vertex $$$2$$$, but butterfly on vertex $$$3$$$ doesn't move. The distance between vertices $$$2$$$ and $$$3$$$ is $$$1$$$.

 Edges are $$$1 \rightarrow 2$$$ and $$$3 \rightarrow 2$$$: butterfly on vertex $$$1$$$ moves to vertex $$$2$$$, but butterfly on vertex $$$3$$$ can't move to vertex $$$2$$$ because it's occupied. The distance between vertices $$$2$$$ and $$$3$$$ is $$$1$$$.

 Edges are $$$2 \rightarrow 1$$$ and $$$2 \rightarrow 3$$$: butterflies on both vertex $$$1$$$ and vertex $$$3$$$ don't move. The distance between vertices $$$1$$$ and $$$3$$$ is $$$2$$$.

 Edges are $$$2 \rightarrow 1$$$ and $$$3 \rightarrow 2$$$: butterfly on vertex $$$1$$$ doesn't move, but butterfly on vertex $$$3$$$ move to vertex $$$2$$$. The distance between vertices $$$1$$$ and $$$2$$$ is $$$1$$$.

Therefore, the expected value of Koxia's score is $$$\frac {1+1+2+1} {4} = \frac {5} {4}$$$, which is $$$748\,683\,266$$$ after modulo $$$998\,244\,353$$$.

In the second test case, the tree is shown below. Vertices containing butterflies are noted as bold. The expected value of Koxia's score is $$$\frac {11} {6}$$$, which is $$$831\,870\,296$$$ after modulo $$$998\,244\,353$$$.

question:
Imi has an undirected tree with $$$n$$$ vertices where edges are numbered from $$$1$$$ to $$$n-1$$$. The $$$i$$$-th edge connects vertices $$$u_i$$$ and $$$v_i$$$. There are also $$$k$$$ butterflies on the tree. Initially, the $$$i$$$-th butterfly is on vertex $$$a_i$$$. All values of $$$a$$$ are pairwise distinct.
Koxia plays a game as follows:
 -  For $$$i = 1, 2, \dots, n - 1$$$, Koxia set the direction of the $$$i$$$-th edge as $$$u_i \rightarrow v_i$$$ or $$$v_i \rightarrow u_i$$$ with equal probability. -  For $$$i = 1, 2, \dots, n - 1$$$, if a butterfly is on the initial vertex of $$$i$$$-th edge and there is no butterfly on the terminal vertex, then this butterfly flies to the terminal vertex. Note that operations are sequentially in order of $$$1, 2, \dots, n - 1$$$ instead of simultaneously. -  Koxia chooses two butterflies from the $$$k$$$ butterflies with equal probability from all possible $$$\frac{k(k-1)}{2}$$$ ways to select two butterflies, then she takes the distance$$$^\dagger$$$ between the two chosen vertices as her score. Now, Koxia wants you to find the expected value of her score, modulo $$$998\,244\,353^\ddagger$$$.
$$$^\dagger$$$ The distance between two vertices on a tree is the number of edges on the (unique) simple path between them.
$$$^\ddagger$$$ Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input
The first line contains two integers $$$n$$$, $$$k$$$ ($$$2 \leq k \leq n \leq 3 \cdot {10}^5$$$) — the size of the tree and the number of butterflies.
The second line contains $$$k$$$ integers $$$a_1, a_2, \dots, a_k$$$ ($$$1 \leq a_i \leq n$$$) — the initial position of butterflies. It's guaranteed that all positions are distinct.
The $$$i$$$-th line in following $$$n − 1$$$ lines contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$) — the vertices the $$$i$$$-th edge connects.
It is guaranteed that the given edges form a tree.

Output
Output a single integer — the expected value of Koxia's score, modulo $$$998\,244\,353$$$.

Examples
Input
3 2
1 3
1 2
2 3

Output
748683266

Input
5 3
3 4 5
1 2
1 3
2 4
2 5

Output
831870296

Note
In the first test case, the tree is shown below. Vertices containing butterflies are noted as bold.
 ![image](1.png) There are only $$$2$$$ butterflies so the choice of butterflies is fixed. Let's consider the following $$$4$$$ cases:
 -  Edges are $$$1 \rightarrow 2$$$ and $$$2 \rightarrow 3$$$: butterfly on vertex $$$1$$$ moves to vertex $$$2$$$, but butterfly on vertex $$$3$$$ doesn't move. The distance between vertices $$$2$$$ and $$$3$$$ is $$$1$$$. -  Edges are $$$1 \rightarrow 2$$$ and $$$3 \rightarrow 2$$$: butterfly on vertex $$$1$$$ moves to vertex $$$2$$$, but butterfly on vertex $$$3$$$ can't move to vertex $$$2$$$ because it's occupied. The distance between vertices $$$2$$$ and $$$3$$$ is $$$1$$$. -  Edges are $$$2 \rightarrow 1$$$ and $$$2 \rightarrow 3$$$: butterflies on both vertex $$$1$$$ and vertex $$$3$$$ don't move. The distance between vertices $$$1$$$ and $$$3$$$ is $$$2$$$. -  Edges are $$$2 \rightarrow 1$$$ and $$$3 \rightarrow 2$$$: butterfly on vertex $$$1$$$ doesn't move, but butterfly on vertex $$$3$$$ move to vertex $$$2$$$. The distance between vertices $$$1$$$ and $$$2$$$ is $$$1$$$. Therefore, the expected value of Koxia's score is $$$\frac {1+1+2+1} {4} = \frac {5} {4}$$$, which is $$$748\,683\,266$$$ after modulo $$$998\,244\,353$$$.
In the second test case, the tree is shown below. Vertices containing butterflies are noted as bold. The expected value of Koxia's score is $$$\frac {11} {6}$$$, which is $$$831\,870\,296$$$ after modulo $$$998\,244\,353$$$.
 ![image](2.png)

image_tags: Tree Tree

data_split: test