E. There Should Be a Lot of Maximums

problem_index: E

time_limit: 1 second

memory_limit: 256 megabytes

note:
![image](images/cf_1805_E/1.png)
In the first example, after removing edge $$$(1, 2)$$$ no number repeats $$$2$$$ times in any of the resulting subtrees, so the answer is $$$\max(0, 0)=0$$$.
After removing edge $$$(2, 3)$$$, in the bigger subtree, $$$1$$$ is repeated twice, and $$$2$$$ is repeated twice, so the $$$\mathrm{MAD}$$$ of this tree is $$$2$$$.
After removing edge $$$(2, 4)$$$, in the bigger subtree, only the number $$$1$$$ is repeated, and in the second subtree, only one number appears, so the answer is $$$1$$$.
In the second example, if edge $$$1 \leftrightarrow 4$$$ is not removed, then one of the subtrees will have two $$$1$$$, so the answer — $$$1$$$. And if edge $$$1 \leftrightarrow 4$$$ is deleted, both subtrees have no repeating values, so the answer is $$$0$$$.

solutions: ["from collections import defaultdict\r\nimport random\r\nimport sys, os, io\r\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\r\n\r\ndef make_graph(n, m):\r\n    x, s = [0] * (2 * m), [0] * (n + 3)\r\n    for i in range(0, 2 * m, 2):\r\n        u, v = map(int, input().split())\r\n        s[u + 2] += 1\r\n        s[v + 2] += 1\r\n        x[i], x[i + 1] = u, v\r\n    for i in range(3, n + 3):\r\n        s[i] += s[i - 1]\r\n    G = [0] * (2 * m)\r\n    for i in range(2 * m):\r\n        j = x[i] + 1\r\n        G[s[j]] = x[i ^ 1]\r\n        s[j] += 1\r\n    return G, s, x\r\n\r\ndef bfs(s):\r\n    q = [s]\r\n    visit = [0] * (n + 1)\r\n    visit[s] = 1\r\n    parent = [-1] * (n + 1)\r\n    for k in range(n):\r\n        i = q[k]\r\n        for v in range(s0[i], s0[i + 1]):\r\n            j = G[v]\r\n            if not visit[j]:\r\n                q.append(j)\r\n                visit[j] = 1\r\n                parent[j] = i\r\n    return parent\r\n\r\nn = int(input())\r\nG, s0, x = make_graph(n, n - 1)\r\ne = dict()\r\nfor i in range(n - 1):\r\n    u, v = x[2 * i], x[2 * i + 1]\r\n    e[(u, v)], e[(v, u)] = i, i\r\na = [0] + list(map(int, input().split()))\r\nr0 = random.randint(1, pow(2, 30) - 1)\r\nd = defaultdict(lambda : [])\r\nfor i in range(1, n + 1):\r\n    d[a[i] ^ r0].append(i)\r\nans = [0] * (n - 1)\r\ny = list(set(sorted(a[1:])))\r\ny.sort(reverse = True)\r\ny = [i ^ r0 for i in y]\r\nf = 0\r\nfor i in y:\r\n    if len(d[i]) >= 3:\r\n        f = 1\r\n        ans = [i ^ r0] * (n - 1)\r\n        break\r\n    elif len(d[i]) == 2:\r\n        f = 1\r\n        parent = bfs(d[i][0])\r\n        u = [d[i][1]]\r\n        while u[-1] ^ d[i][0]:\r\n            u.append(parent[u[-1]])\r\n        break\r\nif (f and ans[0]) or not f:\r\n    sys.stdout.write(\"\\n\".join(map(str, ans)))\r\n    exit()\r\nc = [-1] * (n + 1)\r\nl0 = len(u)\r\nfor i in range(l0):\r\n    c[u[i]] = i\r\nq = list(u)\r\nfor k in range(n):\r\n    i = q[k]\r\n    for v in range(s0[i], s0[i + 1]):\r\n        j = G[v]\r\n        if c[j] == -1:\r\n            q.append(j)\r\n            c[j] = c[i]\r\na0 = a[u[0]]\r\nans = [a0] * (n - 1)\r\nfor i in range(l0 - 1):\r\n    ans[e[(u[i], u[i + 1])]] = 0\r\nl, r = 0, l0 - 1\r\nfor i in y:\r\n    if i ^ r0 >= a0:\r\n        continue\r\n    if len(d[i]) >= 3:\r\n        ans = [max(i ^ r0, j) for j in ans]\r\n        break\r\n    elif len(d[i]) == 1:\r\n        continue\r\n    l1, r1 = c[d[i][0]], c[d[i][1]]\r\n    if l1 > r1:\r\n        l1, r1 = r1, l1\r\n    while l < l1 and l < r:\r\n        ans[e[(u[l], u[l + 1])]] = i ^ r0\r\n        l += 1\r\n    while r > r1 and l < r:\r\n        ans[e[(u[r], u[r - 1])]] = i ^ r0\r\n        r -= 1\r\nsys.stdout.write(\"\\n\".join(map(str, ans)))", "import io,os\nfrom collections import deque \ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n\ndef main(t):\n\n\n    n = int(input())\n    neigh = [[] for _ in range(n)]\n    edges = {}\n    for i 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[(min(u,v)-1,max(u,v)-1)] = i\n\n        \n\n    arr = list(map(int,input().split()))\n    valid = []\n\n\n    fre = {}\n    for num in arr:\n        if str(num) not in fre:  fre[str(num)] = 0\n        fre[str(num)] += 1\n\n    maxtriple = 0\n\n    for key in fre:\n        if fre[key]==2:   valid.append(int(key))\n        if fre[key] > 2:  maxtriple = max(maxtriple, int(key))\n\n\n\n\n\n\n\n\n    valid.sort(reverse=True)\n\n    while valid and valid[-1] < maxtriple:  valid.pop()\n\n    if len(valid)==0:\n        for _ in range(n-1):  print(maxtriple)\n        return\n\n\n\n\n    k = len(valid)\n\n    represent = {}\n    for i in range(len(valid)):   represent[valid[i]] = i\n    root = 0\n    while arr[root] != valid[0]:   root += 1\n\n    alter = root + 1\n    while arr[alter]!= valid[0]:   alter += 1\n\n\n    valid.append(maxtriple)\n\n    queue = deque()\n    queue.append(root)\n\n\n    children = [[] for _ in range(n)]\n    parent = [-2]*n\n    parent[root] = -1\n\n    while queue:\n        index = queue.popleft()\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    path = [alter]\n\n    while path[-1]!=root:\n        path.append(parent[path[-1]])\n\n\n    m = len(path) \n    gift = [set() for _ in range(m)]\n\n#    print(path)\n\n    for i in range(m-1):\n        index = path[i]\n        if i>0:  son = path[i-1]\n        else:  son = -1\n        queue.append(index)\n\n\n        while queue:\n            j = queue.popleft()\n            if arr[j] in represent:  \n                num = represent[arr[j]]\n                if num in gift[i]:  gift[i].remove(num)\n                else:  gift[i].add(num)\n            for nextj in children[j]:  \n                if nextj==son: continue\n                queue.append(nextj)\n    \n#    print(gift)\n        \n    ans = [-1]*(n-1)    \n            \n    curr = [0]*(k+1)\n\n    mex = 0\n    for i in range(m-1):\n\n        for num in gift[i]:  \n            curr[num] ^= 1\n            if curr[num]==0 and num < mex:   \n                mex = num\n\n       \n        while curr[mex]==1:  mex += 1\n\n\n\n\n        u,v = min(path[i],parent[path[i]]),  max(path[i],parent[path[i]])\n#        print(edges[(u,v)])\n        ans[edges[(u,v)]] = valid[mex]\n\n    for i in range(n-1):\n        if ans[i] < 0:  ans[i] = valid[0]\n\n    for num in ans:\n        print(num)\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,math\r\nimport random\r\nfrom bisect import bisect_left , bisect_right \r\nfrom collections import defaultdict\r\n\r\ndef rd(): return sys.stdin.readline().strip()\r\ndef rdl(typ,sep=\" \"): return list(map(typ, rd().split(sep) if sep else rd()))\r\ndef rdlInt(dlt=0,sep=\" \") : return [int(x)+dlt for x in rd().split(sep)]\r\ndef wt(x,sep=\"\\n\") : sys.stdout.write(str(x) + sep)    # string / num\r\ndef wtBoolUp(x): wt(\"YES\" if x else \"NO\")  # True = YES/ False =NO\r\ndef wtBoolLow(x): wt(\"Yes\" if x else \"No\")  # True = Yes/ False =No\r\ndef wtlArr(arr,sep=\" \"):   # Printt arr in single line\r\n    for x in arr: wt(x, sep) \r\n    wt(\"\")\r\ndef wtlsArr(arr):  # Printt arr in mult lines\r\n    for x in arr: wt(x)\r\ndef wtlsArrArr(arr, sep=\" \"):    # print_ Arrays in multiple lines\r\n    for a in arr: wtlArr(a, sep)\r\n\r\n\r\n# for dfs use this and use 'yield' during dfs and at last\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    return wrappedfunc\r\n\r\n# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\r\n\r\nINF = 10**18\r\nMOD = 10**9 + 7 \r\n\r\n\r\nclass mydefaultdict:  # key is always integer\r\n    def __init__(self,default=int):\r\n        self.RANDOM = random.randint(0,1<<32)\r\n        self.default = default\r\n        self.dict = defaultdict(lambda:default)\r\n    def __getitem__(self,key):\r\n        myKey=self.RANDOM^key\r\n        return self.dict[myKey]\r\n    def __setitem__(self,key,item):\r\n        myKey=self.RANDOM^key\r\n        self.dict[myKey]=item\r\n    def __delitem__(self, key):\r\n        myKey=self.RANDOM^key\r\n        del self.dict[myKey]\r\n    def __iter__(self):\r\n        return iter(i^self.RANDOM for i in self.dict)\r\n    def __contains__(self,key):\r\n        return key^self.RANDOM in self.dict\r\n\r\n\r\ndef myCounter(seq):\r\n    res = mydefaultdict(0)\r\n    for x in seq: \r\n        res[x] +=1\r\n    return res\r\n\r\n\r\nclass mySet():   # key is always integer\r\n    def __init__(self):\r\n        self.RANDOM = random.randint(1<<30, 1<<60)\r\n        self.set = set()\r\n    def __contains__(self, item):\r\n        return item ^ self.RANDOM in self.set\r\n    def add(self, item):\r\n        self.set.add(item ^ self.RANDOM)\r\n    def discard(self, item):\r\n        myKey = item ^ self.RANDOM\r\n        if myKey in self.set:\r\n            self.set.remove(myKey)\r\n    def pop(self):\r\n        return self.st.pop() ^ self.RANDOM\r\n\r\n\r\ndef binPow(a,b,mod) :\r\n    res = 1\r\n    while b :\r\n        if b % 2: \r\n            res = res * a % mod\r\n        a = a * a % mod\r\n        b //= 2\r\n    return res\r\n\r\ndef invMod(x,mod): return pow(x,mod-2,mod)      \r\n\r\ndef getFacts(n,mod):   # O(n)\r\n    fact = [1]*(n+1)\r\n    for i in range(2,n+1): fact[i] = (i*fact[i-1])%mod\r\n    return fact\r\n\r\ndef nCr(n, r, fact, mod) :  # O(logMOD)\r\n    num = fact[n]       # numerator\r\n    den = (fact[r] * fact[n - r]) % mod   # denominator\r\n    return (num * invMod(den, mod)) % mod\r\n\r\ndef lcm(num1,num2):\r\n    hcf = math.gcd(num1,num2)\r\n    lcm_ = (num1*num2)//hcf\r\n    return lcm_\r\n\r\ndef sqrtFloat(num):  # req : https://codeforces.com/contest/1809/problem/B\r\n    l, r = 0 , num\r\n    res = 0\r\n    while l <= r :\r\n        mid = (l+r)//2\r\n        if mid*mid <= num :\r\n            res = mid\r\n            l = mid + 1\r\n        else : #number will be on l side\r\n            r = mid-1\r\n    \r\n    return res + 0.1*(res*res != num)\r\n\r\ndef floorDiv(a,b): return a//b\r\ndef ceilDiv(a,b): return (a+b-1)//b\r\n\r\ndef prefixSum(arr):   # 0 at last of prefix sum\r\n    pref = [0]*(len(arr)+1)\r\n    for i in range(len(arr)): pref[i] = arr[i] + pref[i-1]\r\n    return pref\r\n\r\ndef prefixXor(arr):   # 0 at last of prefix Xor\r\n    pref = [0]*(len(arr)+1)\r\n    for i in range(len(arr)): pref[i] = arr[i] ^ pref[i-1]\r\n    return pref\r\n\r\ndef apNth(n, a=1, d=1) : return a+(n-1)*d\r\ndef apSum(n, a=1, d=1):  return (2*a+(n-1)*d)*n//2\r\ndef apSumMod(n, a=1, d=1, mod=MOD):  return ((2*a+(n-1)*d)*n*invMod(2,mod))%mod\r\ndef apSumRange(l, r, d=1) : return apSum((r-l+1)//d, l, d)\r\ndef apSumRangeMod(l, r, d=1, mod=MOD) : return apSumMod((r-l+1)//d, l, d, mod)\r\n\r\ndef hypot(p1,p2):\r\n    return ((p2[0]-p1[0])**2 + (p2[1]-p1[1])**2)**0.5\r\ndef manhat(p1,p2):\r\n    return abs(p2[0]-p1[0]) + abs(p2[1]-p1[1])\r\n\r\ndef comb(n,r):   # for small x otherwise TC higher\r\n    res = 1\r\n    for i in range(r) : res = res*(n-i)//(i+1)   # res*(n-i) % (i+1) == 0  always\r\n    return res\r\n\r\ndef powerArr(base,n,mod):\r\n    pwr = [1]*(n+1)\r\n    for i in range(1,n+1):\r\n        pwr[i] = (base*pwr[i-1]) % mod\r\n    return pwr\r\n\r\ndef invModArr(n, mod):\r\n    modInv = [1]*(n+1)\r\n    for i in range(2, n+1):  modInv[i] = (modInv[mod % i]*(mod - mod // i)) % mod\r\n    return modInv\r\n\r\ndef cntlk(incArr, k): return bisect_left(incArr, k)   # < k cnt\r\ndef cntleqk(incArr, k): return bisect_right(incArr, k)   # <= k cnt\r\ndef cntgk(incArr, k): return len(incArr) - cntleqk(incArr, k)  # > k cnt\r\ndef cntgeqk(incArr, k): return len(incArr) - cntlk(incArr, k)  # >= k cnt\r\ndef getClosest(num,sortArr,notTake=-INF,notTakeCnt=1):\r\n    idx = bisect_left(sortArr,num)  # find closest to x , not take notTake\r\n    closeArr = []\r\n    for i in range(max(0,idx-2),min(len(sortArr),idx+3)) : # [idx-2,idx-1,idx,idx+1,idx+2]\r\n        if notTakeCnt>0 and sortArr[i] == notTake:\r\n            notTakeCnt -= 1\r\n            continue\r\n        closeArr.append(sortArr[i])\r\n    return min(closeArr, key=lambda x:abs(x-num),default=-INF)\r\n\r\ndef compressSeq(itr, notTake=INF):  # grouping of similar elements\r\n    n = len(itr)\r\n    res = []\r\n    i = 0\r\n    while i < n:\r\n        st = i  # start\r\n        while i+1 <n and itr[i] == itr[i+1] :\r\n            i += 1\r\n        if itr[st] != notTake:\r\n            res.append([itr[st],st,i,i-st+1])\r\n        i += 1\r\n    return res\r\n\r\n# Geometry :\r\ndef getLine(y,m,x):\r\n    c = y-m*x\r\n    return (m,c)\r\n\r\n\r\ndirnsRD = [(0,1),(1,0)]\r\ndirnsLU = [(0,-1),(-1,0)]\r\ndirns = [(0,1),(1,0),(0,-1),(-1,0)]  # RDLU\r\ndirnsDiag = dirns + [(1,1),(1,-1),(-1,1),(-1,-1)]\r\nchessDirns = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]\r\n\r\n\r\ndef cntBits(n):\r\n    n -= ((n >> 1) & 0x5555555555555555)\r\n    n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)\r\n    n = (n + (n >> 4)) & 0x0f0f0f0f0f0f0f0f\r\n    n += ((n >> 8) & 0x00ff00ff00ff00ff)\r\n    n += ((n >> 16) & 0x0000ffff0000ffff)\r\n    n += ((n >> 32) & 0x00000000ffffffff)\r\n    return n & 0x7f\r\ndef lowBit(a) : return a & -a\r\ndef rmvLowBit(a) : return a & (a-1)\r\ndef rmvSelectedBits(mask, remover): return mask & ~remover\r\ndef isSubset(mask, checker): return mask & checker == checker\r\ndef isSuperSet(mask , checker): return mask | checker == mask\r\ndef isRepSumP2(num, x): return cntBits(num) <= x <= num  # num in sum two's power in x moves ?\r\ndef binry(decimal): return bin(decimal).replace('0b', '')\r\ndef deciml(binary): return int(str(binary),2)\r\ndef printAllBin(arr):\r\n    maxLen = len(binry(max(arr)))\r\n    for x in arr:\r\n        curr = binry(x)\r\n        res = \" \".join(list(\"0\"*(maxLen-len(curr))+curr))\r\n        wt( res + f\"   <- {x}\")\r\n\r\ndef c2i(ch,up=0): return ord(ch) - ord('A' if up else 'a')  # ch to integer\r\ndef i2c(n,up=0): return chr(ord('A' if up else 'a') + n)    # integer to ch\r\n\r\ndef setPrecRound(num, cnt): return round(num, cnt)\r\ndef setPrec(num, cnt): return format(num,f\".{cnt}f\")\r\n# Interactive :\r\ndef flush(): sys.stdout.flush()\r\ndef ojAsk(quesArr, anstyp=int, ansIsList=0): \r\n    wt(\"?\",\" \") ; wtlArr(quesArr)\r\n    flush()\r\n    ans = None\r\n    if ansIsList: ans = rdl(anstyp)\r\n    else: ans = anstyp(rd())\r\n    return ans\r\ndef ojAns(ansArr): wt(\"!\",\" \") ; wtlArr(ansArr) ; flush()\r\n\r\ndef clearCache(func): func.cache_clear()   # used to clear the lru cache for every new test case\r\ndef SSS(l, r, isReverse):  # in [l,r] strt,stop,stepsize ; use *in range\r\n    if isReverse:\r\n        return [r, l-1, -1]\r\n    return [l, r+1, 1]\r\n\r\n\r\n# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\r\n\r\n# sys.setrecursionlimit(300_005)\r\n# INF = 10**9  # change from 10**18 to 10**9\r\n# MOD = 10**9 + 7\r\n\r\n\r\ndef solve():\r\n    n = int(rd())\r\n    adjList = [[] for _ in range(n+1)]\r\n    for i in range(n-1):\r\n        u,v = rdlInt(-1)\r\n        adjList[u].append((v,i))\r\n        adjList[v].append((u,i))\r\n    vals = rdl(int)\r\n\r\n    ##  -----------------------------------------  \r\n    \r\n    cnt = defaultdict(int)\r\n    mads = [0]\r\n    for x in vals:\r\n        cnt[x] += 1\r\n        if cnt[x] == 2:\r\n            mads.append(x)\r\n        \r\n\r\n    mads.sort()\r\n    mx = mads[-1]\r\n    res = [mx]*(n-1)\r\n    if mx == 0:   # all values cnt are < 2\r\n        return res  \r\n    if cnt[mx] >= 3:   # mx will be in one of the graph always\r\n        return res\r\n\r\n    # else cnt of mx == 2 and track the nodes in between\r\n    u1, u2 = [i for i in range(n) if vals[i] == mx]\r\n\r\n    ## Find the Path edges b/w u1 and u2\r\n    # Go from i to j and mark the parents\r\n    parent = [(-1,-1)]*n\r\n    stack = [u1]\r\n    while stack:\r\n        root = stack.pop()\r\n        if root == u2:\r\n            break\r\n        for child,ei in adjList[root]:\r\n            if parent[child] == (-1,-1):\r\n                parent[child] = (root,ei)\r\n                stack.append(child)\r\n\r\n    # Go from u2 to u1 by parents and mark in b/w edges\r\n    mark = [False]*n\r\n    path = []\r\n    v = u2\r\n    while v != u1 :\r\n        par,ei = parent[v]\r\n        mark[ei] = True\r\n        path.append((par,ei))\r\n        v = par\r\n\r\n    path.reverse()   # u1 -> u2 path\r\n\r\n    # Now start from u and keep dividing the graph in two parts \r\n    # newPart will be expand and old will be shrink so maintain cnt and mx for new one\r\n    cntNew = defaultdict(int)\r\n    mxNew = 0\r\n    sti = len(mads)-1   # to track the new maximum value set to maximum initially once goes in old never be back\r\n    for u,ei in path:   # visiting the edges one by one u->v\r\n        stack = [u]\r\n        while stack:\r\n            root = stack.pop()\r\n            x = vals[root]\r\n            cnt[x] -= 1\r\n            cntNew[x] += 1\r\n            if cntNew[x] == 2 and x > mxNew:\r\n                mxNew = x\r\n            for child,cei in adjList[root]:\r\n                if mark[cei]: \r\n                    continue\r\n                stack.append(child)\r\n                mark[cei] = True\r\n\r\n        while sti>0 and cnt[mads[sti]] < 2:  # need to stop at 0\r\n            sti -= 1\r\n            mx = mads[sti]\r\n        \r\n        res[ei] = max(mxNew, mx)\r\n\r\n\r\n    return res\r\n\r\n\r\n# Don't forget the mod and recursion limit and INF\r\n\r\nwtlsArr(solve())", "import sys,math\r\nimport random\r\nfrom bisect import bisect_left , bisect_right \r\nfrom heapq import heappush, heappop, heapify\r\nfrom collections import defaultdict, Counter, deque\r\nfrom functools import lru_cache\r\nfrom itertools import product\r\n\r\n\r\ndef rd(): return sys.stdin.readline().strip()\r\ndef rdl(typ,sep=\" \"): return list(map(typ, rd().split(sep) if sep else rd()))\r\ndef rdlInt(dlt=0,sep=\" \") : return [int(x)+dlt for x in rd().split(sep)]\r\ndef wt(x,sep=\"\\n\") : sys.stdout.write(str(x) + sep)    # string / num\r\ndef wtBoolUp(x): wt(\"YES\" if x else \"NO\")  # True = YES/ False =NO\r\ndef wtBoolLow(x): wt(\"Yes\" if x else \"No\")  # True = Yes/ False =No\r\ndef wtlArr(arr,sep=\" \"):   # Printt arr in single line\r\n    for x in arr: wt(x, sep) \r\n    wt(\"\")\r\ndef wtlsArr(arr):  # Printt arr in mult lines\r\n    for x in arr: wt(x)\r\ndef wtlsArrArr(arr, sep=\" \"):    # print_ Arrays in multiple lines\r\n    for a in arr: wtlArr(a, sep)\r\n\r\n\r\n# for dfs use this and use 'yield' during dfs and at last\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    return wrappedfunc\r\n\r\n# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\r\n\r\nINF = 10**18\r\nMOD = 10**9 + 7 \r\n\r\n\r\nclass mydefaultdict:  # key is always integer\r\n    def __init__(self,default=int):\r\n        self.RANDOM = random.randint(0,1<<32)\r\n        self.default = default\r\n        self.dict = defaultdict(lambda:default)\r\n    def __getitem__(self,key):\r\n        myKey=self.RANDOM^key\r\n        return self.dict[myKey]\r\n    def __setitem__(self,key,item):\r\n        myKey=self.RANDOM^key\r\n        self.dict[myKey]=item\r\n    def __delitem__(self, key):\r\n        myKey=self.RANDOM^key\r\n        del self.dict[myKey]\r\n    def __iter__(self):\r\n        return iter(i^self.RANDOM for i in self.dict)\r\n    def __contains__(self,key):\r\n        return key^self.RANDOM in self.dict\r\n\r\n\r\ndef myCounter(seq):\r\n    res = mydefaultdict(0)\r\n    for x in seq: \r\n        res[x] +=1\r\n    return res\r\n\r\n\r\nclass mySet():   # key is always integer\r\n    def __init__(self):\r\n        self.RANDOM = random.randint(1<<30, 1<<60)\r\n        self.set = set()\r\n    def __contains__(self, item):\r\n        return item ^ self.RANDOM in self.set\r\n    def add(self, item):\r\n        self.set.add(item ^ self.RANDOM)\r\n    def discard(self, item):\r\n        myKey = item ^ self.RANDOM\r\n        if myKey in self.set:\r\n            self.set.remove(myKey)\r\n    def pop(self):\r\n        return self.st.pop() ^ self.RANDOM\r\n\r\n\r\ndef binPow(a,b,mod) :\r\n    res = 1\r\n    while b :\r\n        if b % 2: \r\n            res = res * a % mod\r\n        a = a * a % mod\r\n        b //= 2\r\n    return res\r\n\r\ndef invMod(x,mod): return pow(x,mod-2,mod)      \r\n\r\ndef getFacts(n,mod):   # O(n)\r\n    fact = [1]*(n+1)\r\n    for i in range(2,n+1): fact[i] = (i*fact[i-1])%mod\r\n    return fact\r\n\r\ndef nCr(n, r, fact, mod) :  # O(logMOD)\r\n    num = fact[n]       # numerator\r\n    den = (fact[r] * fact[n - r]) % mod   # denominator\r\n    return (num * invMod(den, mod)) % mod\r\n\r\ndef lcm(num1,num2):\r\n    hcf = math.gcd(num1,num2)\r\n    lcm_ = (num1*num2)//hcf\r\n    return lcm_\r\n\r\ndef sqrtFloat(num):  # req : https://codeforces.com/contest/1809/problem/B\r\n    l, r = 0 , num\r\n    res = 0\r\n    while l <= r :\r\n        mid = (l+r)//2\r\n        if mid*mid <= num :\r\n            res = mid\r\n            l = mid + 1\r\n        else : #number will be on l side\r\n            r = mid-1\r\n    \r\n    return res + 0.1*(res*res != num)\r\n\r\ndef floorDiv(a,b): return a//b\r\ndef ceilDiv(a,b): return (a+b-1)//b\r\n\r\ndef prefixSum(arr):   # 0 at last of prefix sum\r\n    pref = [0]*(len(arr)+1)\r\n    for i in range(len(arr)): pref[i] = arr[i] + pref[i-1]\r\n    return pref\r\n\r\ndef prefixXor(arr):   # 0 at last of prefix Xor\r\n    pref = [0]*(len(arr)+1)\r\n    for i in range(len(arr)): pref[i] = arr[i] ^ pref[i-1]\r\n    return pref\r\n\r\ndef apNth(n, a=1, d=1) : return a+(n-1)*d\r\ndef apSum(n, a=1, d=1):  return (2*a+(n-1)*d)*n//2\r\ndef apSumMod(n, a=1, d=1, mod=MOD):  return ((2*a+(n-1)*d)*n*invMod(2,mod))%mod\r\ndef apSumRange(l, r, d=1) : return apSum((r-l+1)//d, l, d)\r\ndef apSumRangeMod(l, r, d=1, mod=MOD) : return apSumMod((r-l+1)//d, l, d, mod)\r\n\r\ndef hypot(p1,p2):\r\n    return ((p2[0]-p1[0])**2 + (p2[1]-p1[1])**2)**0.5\r\ndef manhat(p1,p2):\r\n    return abs(p2[0]-p1[0]) + abs(p2[1]-p1[1])\r\n\r\ndef comb(n,r):   # for small x otherwise TC higher\r\n    res = 1\r\n    for i in range(r) : res = res*(n-i)//(i+1)   # res*(n-i) % (i+1) == 0  always\r\n    return res\r\n\r\ndef powerArr(base,n,mod):\r\n    pwr = [1]*(n+1)\r\n    for i in range(1,n+1):\r\n        pwr[i] = (base*pwr[i-1]) % mod\r\n    return pwr\r\n\r\ndef invModArr(n, mod):\r\n    modInv = [1]*(n+1)\r\n    for i in range(2, n+1):  modInv[i] = (modInv[mod % i]*(mod - mod // i)) % mod\r\n    return modInv\r\n\r\ndef cntlk(incArr, k): return bisect_left(incArr, k)   # < k cnt\r\ndef cntleqk(incArr, k): return bisect_right(incArr, k)   # <= k cnt\r\ndef cntgk(incArr, k): return len(incArr) - cntleqk(incArr, k)  # > k cnt\r\ndef cntgeqk(incArr, k): return len(incArr) - cntlk(incArr, k)  # >= k cnt\r\ndef getClosest(num,sortArr,notTake=-INF,notTakeCnt=1):\r\n    idx = bisect_left(sortArr,num)  # find closest to x , not take notTake\r\n    closeArr = []\r\n    for i in range(max(0,idx-2),min(len(sortArr),idx+3)) : # [idx-2,idx-1,idx,idx+1,idx+2]\r\n        if notTakeCnt>0 and sortArr[i] == notTake:\r\n            notTakeCnt -= 1\r\n            continue\r\n        closeArr.append(sortArr[i])\r\n    return min(closeArr, key=lambda x:abs(x-num),default=-INF)\r\n\r\ndef compressSeq(itr, notTake=INF):  # grouping of similar elements\r\n    n = len(itr)\r\n    res = []\r\n    i = 0\r\n    while i < n:\r\n        st = i  # start\r\n        while i+1 <n and itr[i] == itr[i+1] :\r\n            i += 1\r\n        if itr[st] != notTake:\r\n            res.append([itr[st],st,i,i-st+1])\r\n        i += 1\r\n    return res\r\n\r\n# Geometry :\r\ndef getLine(y,m,x):\r\n    c = y-m*x\r\n    return (m,c)\r\n\r\n\r\ndirnsRD = [(0,1),(1,0)]\r\ndirnsLU = [(0,-1),(-1,0)]\r\ndirns = [(0,1),(1,0),(0,-1),(-1,0)]  # RDLU\r\ndirnsDiag = dirns + [(1,1),(1,-1),(-1,1),(-1,-1)]\r\nchessDirns = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]\r\n\r\n\r\ndef cntBits(n):\r\n    n -= ((n >> 1) & 0x5555555555555555)\r\n    n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)\r\n    n = (n + (n >> 4)) & 0x0f0f0f0f0f0f0f0f\r\n    n += ((n >> 8) & 0x00ff00ff00ff00ff)\r\n    n += ((n >> 16) & 0x0000ffff0000ffff)\r\n    n += ((n >> 32) & 0x00000000ffffffff)\r\n    return n & 0x7f\r\ndef lowBit(a) : return a & -a\r\ndef rmvLowBit(a) : return a & (a-1)\r\ndef rmvSelectedBits(mask, remover): return mask & ~remover\r\ndef isSubset(mask, checker): return mask & checker == checker\r\ndef isSuperSet(mask , checker): return mask | checker == mask\r\ndef isRepSumP2(num, x): return cntBits(num) <= x <= num  # num in sum two's power in x moves ?\r\ndef binry(decimal): return bin(decimal).replace('0b', '')\r\ndef deciml(binary): return int(str(binary),2)\r\ndef printAllBin(arr):\r\n    maxLen = len(binry(max(arr)))\r\n    for x in arr:\r\n        curr = binry(x)\r\n        res = \" \".join(list(\"0\"*(maxLen-len(curr))+curr))\r\n        wt( res + f\"   <- {x}\")\r\n\r\ndef c2i(ch,up=0): return ord(ch) - ord('A' if up else 'a')  # ch to integer\r\ndef i2c(n,up=0): return chr(ord('A' if up else 'a') + n)    # integer to ch\r\n\r\ndef setPrecRound(num, cnt): return round(num, cnt)\r\ndef setPrec(num, cnt): return format(num,f\".{cnt}f\")\r\n# Interactive :\r\ndef flush(): sys.stdout.flush()\r\ndef ojAsk(quesArr, anstyp=int, ansIsList=0): \r\n    wt(\"?\",\" \") ; wtlArr(quesArr)\r\n    flush()\r\n    ans = None\r\n    if ansIsList: ans = rdl(anstyp)\r\n    else: ans = anstyp(rd())\r\n    return ans\r\ndef ojAns(ansArr): wt(\"!\",\" \") ; wtlArr(ansArr) ; flush()\r\n\r\ndef clearCache(func): func.cache_clear()   # used to clear the lru cache for every new test case\r\ndef SSS(l, r, isReverse):  # in [l,r] strt,stop,stepsize ; use *in range\r\n    if isReverse:\r\n        return [r, l-1, -1]\r\n    return [l, r+1, 1]\r\n\r\n\r\n# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\r\n\r\n# sys.setrecursionlimit(300_005)\r\n# INF = 10**9  # change from 10**18 to 10**9\r\n# MOD = 10**9 + 7\r\n\r\n\r\ndef solve():\r\n    n = int(rd())\r\n    adjList = [[] for _ in range(n+1)]\r\n    for i in range(n-1):\r\n        u,v = rdlInt(-1)\r\n        adjList[u].append((v,i))\r\n        adjList[v].append((u,i))\r\n    vals = rdl(int)\r\n\r\n    ##  -----------------------------------------  \r\n    \r\n    cnt = defaultdict(int)\r\n    mads = [0]\r\n    for x in vals:\r\n        cnt[x] += 1\r\n        if cnt[x] == 2:\r\n            mads.append(x)\r\n        \r\n\r\n    mads.sort()\r\n    mx = mads[-1]\r\n    res = [mx]*(n-1)\r\n    if mx == 0:   # all values cnt are < 2\r\n        return res  \r\n    if cnt[mx] > 2:   # mx will be in one of the graph always\r\n        return res\r\n\r\n    # else cnt of mx == 2 and track the nodes in between\r\n    u1, u2 = [i for i in range(n) if vals[i] == mx]\r\n\r\n    ## Find the Path edges b/w u1 and u2\r\n    # Go from i to j and mark the parents\r\n    parent = [(-1,-1)]*n\r\n    stack = [u1]\r\n    while stack:\r\n        root = stack.pop()\r\n        if root == u2:\r\n            break\r\n        for child,ei in adjList[root]:\r\n            if parent[child] == (-1,-1):\r\n                parent[child] = (root,ei)\r\n                stack.append(child)\r\n\r\n    # Go from u2 to u1 by parents and mark in b/w edges\r\n    mark = [False]*n\r\n    path = []\r\n    v = u2\r\n    while v != u1 :\r\n        par,ei = parent[v]\r\n        mark[ei] = True\r\n        path.append((par,ei))\r\n        v = par\r\n\r\n    path.reverse()   # u1 -> u2 path\r\n\r\n    # Now start from u and keep dividing the graph in two parts \r\n    # newPart will be expand and old will be shrink so maintain cnt and mx for new one\r\n    cntNew = defaultdict(int)\r\n    mxNew = 0\r\n    sti = len(mads)-1   # to track the new maximum value set to maximum initially once goes in old never be back\r\n    for u,ei in path:   # visiting the edges one by one u->v\r\n        stack = [u]\r\n        while stack:\r\n            root = stack.pop()\r\n            x = vals[root]\r\n            cnt[x] -= 1\r\n            cntNew[x] += 1\r\n            if cntNew[x] == 2 and x > mxNew:\r\n                mxNew = x\r\n            for child,cei in adjList[root]:\r\n                if mark[cei]: \r\n                    continue\r\n                stack.append(child)\r\n                mark[cei] = True\r\n\r\n        while sti>0 and cnt[mads[sti]] < 2:  # need to stop at 0\r\n            sti -= 1\r\n            mx = mads[sti]\r\n        \r\n        res[ei] = max(mxNew, mx)\r\n\r\n\r\n    return res\r\n\r\n\r\n# Don't forget the mod and recursion limit and INF\r\n\r\nwtlsArr(solve())", "from io import BytesIO, IOBase\r\nimport sys\r\nimport os\r\n\r\n# import time\r\nimport bisect\r\n# import functools\r\nimport math\r\nimport random\r\n# import re\r\nfrom collections import Counter, defaultdict, deque\r\nfrom copy import deepcopy\r\nfrom functools import cmp_to_key, lru_cache, reduce\r\nfrom heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest\r\nfrom itertools import accumulate, combinations, permutations, count, product\r\nfrom operator import add, iand, ior, itemgetter, mul, xor\r\nfrom string import ascii_lowercase, ascii_uppercase\r\nfrom typing import *\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\nBUFSIZE = 5096\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\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, BUFSIZE))\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    def read(self):\r\n        while True:\r\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\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\r\nsys.stdin = IOWrapper(sys.stdin)\r\nsys.stdout = IOWrapper(sys.stdout)\r\ninput = lambda: sys.stdin.readline().rstrip(\"\\r\\n\")\r\n\r\ndef I():\r\n    return input()\r\n\r\ndef II():\r\n    return int(input())\r\n\r\ndef MII():\r\n    return map(int, input().split())\r\n\r\ndef LI():\r\n    return list(input().split())\r\n\r\ndef LII():\r\n    return list(map(int, input().split()))\r\n\r\ndef GMI():\r\n    return map(lambda x: int(x) - 1, input().split())\r\n\r\ndef LGMI():\r\n    return list(map(lambda x: int(x) - 1, input().split()))\r\n\r\ninf = float('inf')\r\n\r\n# from types import GeneratorType\r\n\r\n# def 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#     return wrappedfunc\r\n\r\nRANDOM = random.getrandbits(32)\r\n\r\n# class Wrapper_str(str):\r\n#     def __init__(self, x):\r\n#         str.__init__(x)\r\n\r\n#     def __hash__(self):\r\n#         return super(Wrapper_str, self).__hash__() ^ RANDOM\r\n\r\n# class Wrapper_tuple(tuple):\r\n#     def __init__(self, x):\r\n#         tuple.__init__(x)\r\n\r\n#     def __hash__(self):\r\n#         return super(Wrapper_tuple, self).__hash__() ^ RANDOM\r\n\r\nclass Wrapper_int(int):\r\n    def __init__(self, x):\r\n        int.__init__(x)\r\n\r\n    def __hash__(self):\r\n        return super(Wrapper_int, self).__hash__() ^ RANDOM\r\n\r\ndef dfs(u):\r\n    parent = [-1] * n\r\n    stack = [u]\r\n    while stack:\r\n        u = stack.pop()\r\n        for v in path[u]:\r\n            if parent[u] != v:\r\n                parent[v] = u\r\n                stack.append(v)\r\n    return parent\r\n\r\nn = II()\r\nedges = []\r\npath = [[] for _ in range(n)]\r\nfor _ in range(n - 1):\r\n    u, v = GMI()\r\n    edges.append((u, v))\r\n    path[u].append(v)\r\n    path[v].append(u)\r\nvals = [Wrapper_int(x) for x in MII()]\r\n\r\ncnt = Counter(vals)\r\ndefault = 0\r\ntwice_max = 0\r\nfor v in cnt:\r\n    if cnt[v] >= 3: default = max(default, v)\r\n    elif cnt[v] == 2: twice_max = max(twice_max, v)\r\n\r\n\r\nif default >= twice_max:\r\n    print(*(default for _ in range(n - 1)), sep='\\n')\r\n\r\nelse:\r\n    ans = [max(default, twice_max)] * n\r\n    idx1 = vals.index(twice_max)\r\n    idx2 = vals.index(twice_max, idx1+1)\r\n\r\n    parent = dfs(idx1)\r\n    nodes = [idx2]\r\n    while nodes[-1] != idx1:\r\n        nodes.append(parent[nodes[-1]])\r\n\r\n    k = len(nodes)\r\n\r\n    left = [0] * k\r\n    cnt = Counter()\r\n    for i in range(k):\r\n        left[i] = left[i-1]\r\n        stack = [nodes[i]]\r\n        while stack:\r\n            u = stack.pop()\r\n            cnt[vals[u]] += 1\r\n            if cnt[vals[u]] == 2: left[i] = max(left[i], vals[u])\r\n            for v in path[u]:\r\n                if parent[v] == u and v != nodes[i-1]:\r\n                    stack.append(v)\r\n\r\n    right = [0] * k\r\n    cnt = Counter()\r\n    for i in range(k-2, -1, -1):\r\n        right[i] = right[i+1]\r\n        stack = [nodes[i+1]]\r\n        while stack:\r\n            u = stack.pop()\r\n            cnt[vals[u]] += 1\r\n            if cnt[vals[u]] == 2: right[i] = max(right[i], vals[u])\r\n            for v in path[u]:\r\n                if parent[u] != v and v != nodes[i]:\r\n                    stack.append(v)\r\n\r\n    for i in range(k):\r\n        ans[nodes[i]] = max(left[i], right[i], default)\r\n\r\n    for u, v in edges:\r\n        print(ans[u] if parent[u] == v else ans[v])"]

source: codeforces

raw_problem:
E. There Should Be a Lot of Maximums

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

You are given a tree (a connected graph without cycles). Each vertex of the tree contains an integer. Let's define the $$$\mathrm{MAD}$$$ (maximum double) parameter of the tree as the maximum integer that occurs in the vertices of the tree at least $$$2$$$ times. If no number occurs in the tree more than once, then we assume $$$\mathrm{MAD}=0$$$.

Note that if you remove an edge from the tree, it splits into two trees. Let's compute the $$$\mathrm{MAD}$$$ parameters of the two trees and take the maximum of the two values. Let the result be the value of the deleted edge.

For each edge, find its value. Note that we don't actually delete any edges from the tree, the values are to be found independently.

Input

The first line contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices in the tree.

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) — the ends of an edge of the tree. It's guaranteed that the given edges form a valid tree.

The last line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the numbers in the vertices.

Output

For each edge in the input order, print one number — the maximum of the $$$\mathrm{MAD}$$$ parameters of the two trees obtained after removing the given edge from the initial tree.

Examples

Input

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

Output

0
2
1
2

Input

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

Output

1
1
0
1
1

Note

In the first example, after removing edge $$$(1, 2)$$$ no number repeats $$$2$$$ times in any of the resulting subtrees, so the answer is $$$\max(0, 0)=0$$$.

After removing edge $$$(2, 3)$$$, in the bigger subtree, $$$1$$$ is repeated twice, and $$$2$$$ is repeated twice, so the $$$\mathrm{MAD}$$$ of this tree is $$$2$$$.

After removing edge $$$(2, 4)$$$, in the bigger subtree, only the number $$$1$$$ is repeated, and in the second subtree, only one number appears, so the answer is $$$1$$$.

In the second example, if edge $$$1 \leftrightarrow 4$$$ is not removed, then one of the subtrees will have two $$$1$$$, so the answer — $$$1$$$. And if edge $$$1 \leftrightarrow 4$$$ is deleted, both subtrees have no repeating values, so the answer is $$$0$$$.

question:
You are given a tree (a connected graph without cycles). Each vertex of the tree contains an integer. Let's define the $$$\mathrm{MAD}$$$ (maximum double) parameter of the tree as the maximum integer that occurs in the vertices of the tree at least $$$2$$$ times. If no number occurs in the tree more than once, then we assume $$$\mathrm{MAD}=0$$$.
Note that if you remove an edge from the tree, it splits into two trees. Let's compute the $$$\mathrm{MAD}$$$ parameters of the two trees and take the maximum of the two values. Let the result be the value of the deleted edge.
For each edge, find its value. Note that we don't actually delete any edges from the tree, the values are to be found independently.

Input
The first line contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices in the tree.
Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) — the ends of an edge of the tree. It's guaranteed that the given edges form a valid tree.
The last line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the numbers in the vertices.

Output
For each edge in the input order, print one number — the maximum of the $$$\mathrm{MAD}$$$ parameters of the two trees obtained after removing the given edge from the initial tree.

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

Output
0
2
1
2

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

Output
1
1
0
1
1

Note
 ![image](1.png) In the first example, after removing edge $$$(1, 2)$$$ no number repeats $$$2$$$ times in any of the resulting subtrees, so the answer is $$$\max(0, 0)=0$$$.
After removing edge $$$(2, 3)$$$, in the bigger subtree, $$$1$$$ is repeated twice, and $$$2$$$ is repeated twice, so the $$$\mathrm{MAD}$$$ of this tree is $$$2$$$.
After removing edge $$$(2, 4)$$$, in the bigger subtree, only the number $$$1$$$ is repeated, and in the second subtree, only one number appears, so the answer is $$$1$$$.
In the second example, if edge $$$1 \leftrightarrow 4$$$ is not removed, then one of the subtrees will have two $$$1$$$, so the answer — $$$1$$$. And if edge $$$1 \leftrightarrow 4$$$ is deleted, both subtrees have no repeating values, so the answer is $$$0$$$.

data_split: test


Flashing Fluorescents

difficulty: HARD

source: open kattis

raw_problem:
You have $n$ lights,
    each with its own button, in a line. Pressing a light’s button
    will toggle that light’s state; if the light is on, it will
    turn off, and if the light is off, it will turn on. The lights
    change at $1$ second
    timesteps. You can press a button at any time, but it will not
    take effect until the next timestep. Before each timestep, you
    may choose to push at most one button (you may also choose to
    not press any button).

Pushing a button will affect not just the light in question,
    but all lights down the line. More specifically, if you choose
    to press the $i^\textrm
    {th}$ button right before the $k^\textrm {th}$ timestep, then the
    $(i+m)^\textrm {th}$ light
    will toggle on the $(k+m)^\textrm
    {th}$ timestep (with $i+m
    \le n$). For example, if you press button $5$ just before time $19$, then light $5$ will toggle at time $19$, light $6$ will toggle at time $20$, light $7$ will toggle at time $21$, and so on. If you push a button
    that will take effect at the same time as its light would have
    toggled due to an earlier button press, then the two cancel
    each other out, including subsequent toggles.

Suppose there are three lights, all of which are off at the
    start. If you press the first button before the first timestep,
    this will happen in three timesteps:

Now, suppose you press the first button before the first
    timestep, and then the second button between the first and
    second timesteps. The button press will cancel out the
    propagation, and this will happen (note that the propagation
    will go no further):

    Now, suppose you press the first button before the first
    timestep, and then the third button between the first and
    second timesteps. All three lights will be on at the second
    timestep (but not the third):

You wish to turn on all the lights. What is the earliest
    time you could possibly see all of the lights turned on? Note
    that if the lights are all on at time $t$ but not at time $t+1$ due to this propagation,
    $t$ is still the correct
    answer.

Input

Each input will consist of a single test case. Note that
    your program may be run multiple times on different inputs.
    Each test case will consist of a single string $S$ ($1
    \le |S| \le 16$). The string $S$ will contain only the characters
    $1$ and $0$, where $1$ represents that that light is
    initially on, and $0$
    represents that that light is initially off. The first
    character is light $1$,
    the next is light $2$, and
    so on.

Output

Output a single integer, which is the earliest time at which
    all of the lights are on.

Sample Input 1
Sample Output 1

1101

1

Sample Input 2
Sample Output 2

1

0

Sample Input 3
Sample Output 3

000

2

question:
You have$n$lights, each with its own button, in a line. Pressing a light’s button will toggle that light’s state; if the light is on, it will turn off, and if the light is off, it will turn on. The lights change at$1$second timesteps. You can press a button at any time, but it will not take effect until the next timestep. Before each timestep, you may choose to push at most one button (you may also choose to not press any button).
Pushing a button will affect not just the light in question, but all lights down the line. More specifically, if you choose to press the$i^\textrm {th}$button right before the$k^\textrm {th}$timestep, then the$(i+m)^\textrm {th}$light will toggle on the$(k+m)^\textrm {th}$timestep (with$i+m \le n$). For example, if you press button$5$just before time$19$, then light$5$will toggle at time$19$, light$6$will toggle at time$20$, light$7$will toggle at time$21$, and so on. If you push a button that will take effect at the same time as its light would have toggled due to an earlier button press, then the two cancel each other out, including subsequent toggles.
Suppose there are three lights, all of which are off at the start. If you press the first button before the first timestep, this will happen in three timesteps:
![image](1.png)Now, suppose you press the first button before the first timestep, and then the second button between the first and second timesteps. The button press will cancel out the propagation, and this will happen (note that the propagation will go no further):
![image](2.png)Now, suppose you press the first button before the first timestep, and then the third button between the first and second timesteps. All three lights will be on at the second timestep (but not the third):
![image](3.png)You wish to turn on all the lights. What is the earliest time you could possibly see all of the lights turned on? Note that if the lights are all on at time$t$but not at time$t+1$due to this propagation,$t$is still the correct answer.

Input
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will consist of a single string$S$($1 \le |S| \le 16$). The string$S$will contain only the characters$1$and$0$, where$1$represents that that light is initially on, and$0$represents that that light is initially off. The first character is light$1$, the next is light$2$, and so on.

Output
Output a single integer, which is the earliest time at which all of the lights are on.
Sample Input 1
1101

Sample Output 1
1

Sample Input 2
1

Sample Output 2
0

Sample Input 3
000

Sample Output 3
2

image_tags: Others Others Others

data_split: test


AtCoder Beginner Contest 078 - ISU

solutions: ["(X, Y, Z) = map(int, input().split(' '))\nans = (X - Z) // (Y + Z)\nprint(ans)\n", "(x, y, z) = map(int, input().split())\nx -= z\nr = x // (y + z)\nprint(r)\n", "(X, Y, Z) = list(map(int, input().split()))\nprint((X - Z) // (Z + Y))\n", "def answer(x: int, y: int, z: int) -> int:\n\treturn (x - z) // (y + z)\n\ndef main():\n\t(x, y, z) = map(int, input().split())\n\tprint(answer(x, y, z))\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "(X, Y, Z) = map(int, input().split())\nnew = X - Z\nprint(new // (Y + Z))\n", "(X, Y, Z) = [int(i) for i in input().split()]\nprint((X - Z) // (Y + Z))\n", "(X, Y, Z) = [int(x) for x in input().split()]\nprint((X - Z) // (Y + Z))\n", "(X, Y, Z) = map(int, input().split())\nleft = X - Z\nprint(left // (Y + Z))\n", "(X, Y, Z) = map(int, input().split())\nhaba = X - Z\nmix = Y + Z\nprint(int(haba / mix))\n", "(x, y, z) = map(int, input().split())\nwidth = y + z\nprint((x - z) // width)\n", "(x, y, z) = map(int, input().split())\nx -= z\nans = x // (y + z)\nrem = x % (y + z)\nprint(ans)\n", "(X, Y, Z) = list(map(int, input().split()))\nans = 0\nfor i in range(1, 10 ** 5):\n\tif X - Y * i - Z * (i + 1) >= 0:\n\t\tans = i\n\t\tcontinue\n\telse:\n\t\tbreak\nprint(ans)\n", "(x, y, z) = map(int, input().split())\nn = (x - z) // (z + y)\nprint(n)\n", "(x, y, z) = map(int, input().split())\nisu = x - z\nprint(isu // (z + y))\n", "(X, Y, Z) = map(int, input().split())\nN = (X - Z) // (Y + Z)\nprint(N)\n", "(X, Y, Z) = map(int, input().split())\na = (X - Z) // (Y + Z)\nprint(a)\n", "(x, y, z) = map(int, input().split())\nanswer = (x - z) // (y + z)\nprint(answer)\n", "(x, y, z) = input().split()\nprint((int(x) - int(z)) // (int(y) + int(z)))\n", "(x, y, z) = list(map(int, input().split()))\nx -= z\ny += z\nprint(x // y)\n", "(X, Y, Z) = [int(s) for s in input().split()]\nprint((X - Z) // (Z + Y))\n", "(x, y, z) = map(int, input().split())\nxx = x - z\nyy = y + z\nprint(int(xx / yy))\n", "(x, y, z) = [int(x) for x in input().split()]\nprint((x - z) // (y + z))\n", "(X, Y, Z) = map(int, input().split())\nprint((X - (Y + 2 * Z)) // (Y + Z) + 1)\n", "(space, seat, sp) = map(int, input().split())\nprint((space - sp) // (seat + sp))\n", "(X, Y, Z) = map(int, input().split())\nL = X - Z\nans = 0\nfor i in range(1000000):\n\tif L >= (Z + Y) * i:\n\t\tans = i\n\telse:\n\t\tbreak\nprint(ans)\n", "(A, B, C) = map(int, input().split())\nprint((A - C) // (B + C))\n", "import math\n(X, Y, Z) = list(map(int, input().split()))\nX -= Z\nprint(math.floor(X / (Y + Z)))\n", "a = list(map(int, input().split()))\nprint((a[0] - a[2]) // (a[1] + a[2]))\n", "(X, Y, Z) = map(int, input().split())\nh = X - Z\ny = Y + Z\nprint(h // y)\n", "(x, y, z) = map(int, input().split())\none_length = y + z\nprint(int((x - z) / one_length))\n", "(x, y, z) = map(int, input().split())\nx -= y + 2 * z\nprint(1 + x // (y + z))\n", "(x, y, z) = map(int, input().split())\nw = x - z\nprint(w // (y + z))\n", "(a, b, c) = list(map(int, input().split()))\nd = a - c\nprint(int(d / (b + c)))\n", "(x, y, z) = map(int, input().split())\nl = [z]\nper = (x - z) // (y + z)\nprint(per)\n", "(a, b, c) = map(int, input().split())\nprint((a - b - c * 2) // (b + c) + 1)\n", "(n, a, b) = [int(i) for i in input().split()]\nprint((n - b) // (a + b))\n", "(x, y, z) = map(int, input().split())\nx -= y + 2 * z\nans = 1\nwhile x - (y + z) >= 0:\n\tans += 1\n\tx -= y + z\nprint(ans)\n", "(x, y, z) = map(int, input().split())\nw = y + z\nprint(x // w if x % w >= z else x // w - 1)\n", "(a, b, c) = input().split()\na = int(a)\nb = int(b)\nc = int(c)\nprint((a - c) // (b + c))\n", "(X, Y, Z) = map(int, input().split())\nn = int((X - Z) / (Y + Z))\nprint(n)\n", "(x, y, z) = map(int, input().split())\nx -= z\ncount = 0\nwhile x >= y + z:\n\tx -= y + z\n\tcount += 1\nprint(count)\n", "(x, y, z) = map(int, input().split())\ncnt = 0\nlength = x - 2 * z\ncnt += length // (y + z)\nlength = length % (y + z)\nif y <= length:\n\tcnt += 1\nprint(cnt)\n", "def answer(x: int, y: int, z: int) -> int:\n\treturn len(range(y + z * 2, x + 1, y + z))\n\ndef main():\n\t(x, y, z) = map(int, input().split())\n\tprint(answer(x, y, z))\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "(x, y, z) = map(int, input().split())\na = x - z\nb = a // (y + z)\nprint(b)\n", "(x, y, z) = list(map(int, input().split()))\nans = 0\nfor i in range(x):\n\tif y * i + z * (i + 1) <= x:\n\t\tans = max(ans, i)\nprint(ans)\n", "x = list(map(int, input().split()))\nprint(int((x[0] - x[2]) / (x[1] + x[2])))\n", "(X, Y, Z) = [int(i) for i in input().split()]\nn = X // (Y + Z)\nm = X % (Y + Z)\nif m >= Z:\n\tprint(n)\nelse:\n\tprint(n - 1)\n", "(x, y, z) = map(int, input().split())\nfor ans in range(1, 100000):\n\tif ans * y + (ans + 1) * z <= x < (ans + 1) * y + (ans + 2) * z:\n\t\tprint(ans)\n\t\treturn\n", "import sys\nimport math\nimport itertools\nimport collections\nimport heapq\nimport re\nimport numpy as np\nfrom functools import reduce\nrr = lambda : sys.stdin.readline().rstrip()\nrs = lambda : sys.stdin.readline().split()\nri = lambda : int(sys.stdin.readline())\nrm = lambda : list(map(int, sys.stdin.readline().split()))\nrl = lambda : list(map(int, sys.stdin.readline().split()))\ninf = float('inf')\nmod = 10 ** 9 + 7\n(a, b, c) = rm()\nprint((a - c) // (b + c))\n", "def mapt(fn, *args):\n\treturn tuple(map(fn, *args))\n\ndef Input():\n\treturn mapt(int, input().split(' '))\n\ndef main():\n\t(x, y, z) = Input()\n\tpeople = x // y\n\tspaces = (people + 1) * z\n\twhile True:\n\t\tif people * y + spaces <= x:\n\t\t\tprint(people)\n\t\t\treturn\n\t\tpeople -= 1\n\t\tspaces = (people + 1) * z\nmain()\n", "(x, y, z) = map(int, input().split())\nlen = x - z\nprint(len // (y + z))\n", "(x, y, z) = map(int, input().split())\nresult = 0\nwhile y * result + z * (result + 1) <= x:\n\tresult += 1\nprint(result - 1)\n", "(x, y, z) = map(int, input().split())\np = (x - z) // (y + z)\nprint(p)\n", "def main():\n\t(X, Y, Z) = list(map(int, input().split()))\n\trest = X - Z\n\tc = 0\n\twhile rest > 0:\n\t\trest = rest - Y - Z\n\t\tif rest < 0:\n\t\t\tprint(c)\n\t\t\treturn\n\t\telif rest == 0:\n\t\t\tprint(c + 1)\n\t\t\treturn\n\t\telse:\n\t\t\tc += 1\nmain()\n", "(X, Y, Z) = [int(_) for _ in input().split()]\nprint((X - Z) // (Y + Z))\n", "(a, b, c) = (int(i) for i in input().split())\nprint((a - c) // (b + c))\n", "def main():\n\t(x, y, z) = list(map(int, input().split()))\n\tx -= y + z * 2\n\tans = 0\n\tif x < 0:\n\t\treturn ans\n\twhile x >= 0:\n\t\tans += 1\n\t\tx -= y + z\n\tprint(ans)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "(x, y, z) = map(int, input().split())\nret = (x - z) // (y + z)\nprint(ret)\n", "(x, y, z) = map(int, input().split())\nfor i in range(100000):\n\tif (i + 1) * z + i * y > x:\n\t\tprint(i - 1)\n\t\tbreak\n", "(x, y, z) = list(map(int, input().split()))\ni = 1\nwhile True:\n\tif (y + z) * i + z > x:\n\t\tprint(i - 1)\n\t\tbreak\n\ti += 1\n", "(x, y, z) = map(int, input().split())\nm = x - z\nprint(m // (y + z))\n", "lst = input().split()\nx = int(lst[0])\ny = int(lst[1])\nz = int(lst[2])\nx -= z\nprint(x // (y + z))\n", "(X, Y, Z) = (int(T) for T in input().split())\nprint((X - Z) // (Y + Z))\n", "(x, y, z) = map(int, input().split())\nn = [i for i in range(z, x - z, y + z)]\nif n[-1] + y + z <= x:\n\tprint(len(n))\nelse:\n\tprint(len(n) - 1)\n", "(X, Y, Z) = map(int, input().split())\nk = (X - Z) // (Z + Y)\nprint(k)\n", "(x, y, z) = map(int, input().split())\nyz = y + z\nx -= z\nprint(x // yz)\n", "(x, y, z) = map(int, input().split())\nn = 0\nwhile True:\n\tif n * y + (n + 1) * z > x:\n\t\tprint(n - 1)\n\t\treturn\n\tn += 1\n", "(X, Y, Z) = map(int, input().split())\nr = (X - Z) // (Y + Z)\nprint(r)\n", "(X, Y, Z) = map(int, input().split())\nX_ = X - Z\nprint(X_ // (Y + Z))\n", "(x, y, z) = map(int, input().split())\nres = (x - z) // (y + z)\nprint(res)\n", "(X, Y, Z) = map(int, input().split())\nA = X - Z\nB = Y + Z\nprint(A // B)\n", "(x, y, z) = (int(i) for i in input().split())\nans = 0\nwhile True:\n\tx -= y + z\n\tif x - z >= 0:\n\t\tans += 1\n\telse:\n\t\tbreak\nprint(ans)\n", "import sys\nsys.setrecursionlimit(10 ** 7)\n\ndef I():\n\treturn int(sys.stdin.readline().rstrip())\n\ndef MI():\n\treturn list(map(int, sys.stdin.readline().rstrip().split()))\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().rstrip().split()))\n\ndef LI2():\n\treturn list(map(int, sys.stdin.readline().rstrip()))\n\ndef S():\n\treturn sys.stdin.readline().rstrip()\n\ndef LS():\n\treturn list(sys.stdin.readline().rstrip().split())\n\ndef LS2():\n\treturn list(sys.stdin.readline().rstrip())\n(X, Y, Z) = MI()\nX -= Z\nprint(X // (Y + Z))\n", "(X, Y, Z) = map(int, input().split())\nm = X - Z\nprint(m // (Y + Z))\n", "(X, Y, Z) = map(int, input().split())\ntmp = X - Z\nprint(tmp // (Y + Z))\n", "(x, y, z) = map(int, input().split())\nprint(len(range(z + y, x - z + 1, z + y)))\n", "(x, y, z) = map(int, input().split())\ncnt = 1\nx -= y + 2 * z\nwhile x >= y + z:\n\tcnt += 1\n\tx -= y + z\nprint(cnt)\n", "(x, y, z) = map(int, input().split())\nx -= z\ncount = x // (y + z)\nprint(count)\n", "import math\n(x, y, z) = map(int, input().split())\nprint(int(math.floor((x - z) / (y + z))))\n", "(x, y, z) = list(map(int, input().split()))\nb = x - z\nc = y + z\nprint(b // c)\n", "(x, y, z) = map(int, input().split())\nnum = x // (y + z)\nif x >= num * y + (num * z + z):\n\tprint(num)\nelse:\n\tprint(num - 1)\n", "(X, Y, Z) = map(int, input().split())\nX = X - Z\nA = X / (Y + Z) // 1\nprint(round(A))\n", "(a, s, d) = map(int, input().split())\nprint((a - d) // (s + d))\n", "(a, b, c) = map(int, input().split())\nfor i in range(a):\n\tif b * (i + 1) + c * (i + 2) > a:\n\t\tprint(i)\n\t\treturn\n", "(x, y, z) = map(int, input().split())\nans = 0\ni = 1\nwhile 1:\n\thaba = i * y + (i + 1) * z\n\tif haba > x:\n\t\tbreak\n\telse:\n\t\tans = i\n\ti += 1\nprint(ans)\n", "(x, y, z) = map(int, input().split())\nsum = y + z + z\nif x < sum:\n\tprint(0)\nelse:\n\tans = 1\n\twhile sum <= x:\n\t\tsum += y + z\n\t\tans += 1\n\tprint(ans - 1)\n", "(x, y, z) = map(int, input().split())\nX = x - z\nans = X // (y + z)\nprint(ans)\n", "(X, Y, Z) = map(int, input().split())\nX_new = X - Z\nprint(int(X_new / (Z + Y)))\n", "(X, Y, Z) = map(int, input().split())\nanswer = (X - Z) // (Y + Z)\nprint(answer)\n", "(a, b, c) = map(int, input().split())\na -= c\nn = a // (b + c)\nprint(n)\n", "(X, Y, Z) = map(int, input().split())\np = X - Z\na = Z + Y\nans = p // a\nprint(ans)\n", "(x, y, z) = map(int, input().split())\nans = 0\nprint((x - z) // (y + z))\n", "(x, y, z) = [int(i) for i in input().split()]\nans = x // (y + z)\nif x - ans * (y + z) < z:\n\tans -= 1\nprint(ans)\n", "(X, Y, Z) = map(int, input().split())\nl = X - Z\nprint(l // (Y + Z))\n", "(a, b, c) = map(int, input().split())\na = a - c\nprint(round(a // (b + c)))\n", "a = list(map(int, input().split()))\nx = 0\ncount = 0\nwhile a[0] - a[2] >= x:\n\tx += a[1]\n\tx += a[2]\n\tcount += 1\nprint(count - 1)\n", "(x, y, z) = map(int, input().split())\nc = (x - z) // (y + z)\nprint(c)\n", "import sys\nsys.setrecursionlimit(10 ** 6)\n(x, y, z) = list(map(int, input().split()))\nprint((x - z) // (y + z))\n", "(x, y, z) = map(int, input().split())\ntmp = (x - z) // (y + z)\namari = (x - z) % (y + z)\nprint(tmp)\n", "(a, b, c) = map(int, input().split())\nX = a - c\nY = b + c\nprint(X // Y)\n"]

difficulty: EASY

source: atcoder

time_limit: 2.0 seconds

memory_limit: 256.0 megabytes

raw_problem:
配点 : <var>200</var> 点

問題文

幅 <var>X</var> センチメートルの椅子があります。
この椅子に座りたい人がたくさんおり，人は椅子に座ると必ず <var>Y</var> センチメートルの幅を使って座ります。

出来る限りたくさんの人を椅子に座らせたいですが，
人はみなシャイなので，人と人の間，また椅子の端と人の間には，
少なくとも <var>Z</var> センチメートル間を開ける必要があります。

最大で何人座ることができますか？

制約

入力は全て整数

<var>1 \leq X, Y, Z \leq 10^5</var>

<var>Y+2Z \leq X</var>

入力

入力は以下の形式で標準入力から与えられる。

<var>X</var> <var>Y</var> <var>Z</var>

出力

求めた答えを出力してください。

入力例 1

13 3 1

出力例 1

3

下図のように座れば，ぴったし <var>3</var> 人座ることが出来ます。

図

入力例 2

12 3 1

出力例 2

2

入力例 3

100000 1 1

出力例 3

49999

入力例 4

64146 123 456

出力例 4

110

入力例 5

64145 123 456

出力例 5

109

Score : <var>200</var> points

Problem Statement

We have a long seat of width <var>X</var> centimeters.
There are many people who wants to sit here. A person sitting on the seat will always occupy an interval of length <var>Y</var> centimeters.

We would like to seat as many people as possible, but they are all very shy, and there must be a gap of length at least <var>Z</var> centimeters between two people, and between the end of the seat and a person.

At most how many people can sit on the seat?

Constraints

All input values are integers.

<var>1 \leq X, Y, Z \leq 10^5</var>

<var>Y+2Z \leq X</var>

Input

Input is given from Standard Input in the following format:

<var>X</var> <var>Y</var> <var>Z</var>

Output

Print the answer.

Sample Input 1

13 3 1

Sample Output 1

3

There is just enough room for three, as shown below:

Figure

Sample Input 2

12 3 1

Sample Output 2

2

Sample Input 3

100000 1 1

Sample Output 3

49999

Sample Input 4

64146 123 456

Sample Output 4

110

Sample Input 5

64145 123 456

Sample Output 5

109

question:
We have a long seat of width $X$ centimeters.
There are many people who wants to sit here. A person sitting on the seat will always occupy an interval of length $Y$ centimeters.
We would like to seat as many people as possible, but they are all very shy, and there must be a gap of length at least $Z$ centimeters between two people, and between the end of the seat and a person.
At most how many people can sit on the seat?

Constraints

- All input values are integers.
- $1 \leq X, Y, Z \leq 10^5$
- $Y+2Z \leq X$

Input
Input is given from Standard Input in the following format:
$X$ $Y$ $Z$

Output
Print the answer.

Sample Input 1
13 3 1

Sample Output 1
3

There is just enough room for three, as shown below:

![image](1.png)
Figure

Sample Input 2
12 3 1

Sample Output 2
2

Sample Input 3
100000 1 1

Sample Output 3
49999

Sample Input 4
64146 123 456

Sample Output 4
110

Sample Input 5
64145 123 456

Sample Output 5
109

data_split: test