Xenia and Tree (Codeforces 342E)
Tags: Others, divide and conquer

Xenia the programmer has a tree consisting of n nodes. We will consider the tree nodes indexed from 1 to n. We will also consider the first node to be initially painted red, and the other nodes — to be painted blue.The distance between two tree nodes v and u is the number of edges in the shortest path between v and u.Xenia needs to learn how to quickly execute queries of two types:  paint a specified blue node in red;  calculate which red node is the closest to the given one and print the shortest distance to the closest red node. Your task is to write a program which will execute the described queries.

Input: The first line contains two integers n and m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105) — the number of nodes in the tree and the number of queries. Next n - 1 lines contain the tree edges, the i-th line contains a pair of integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — an edge of the tree.Next m lines contain queries. Each query is specified as a pair of integers ti, vi (1 ≤ ti ≤ 2, 1 ≤ vi ≤ n). If ti = 1, then as a reply to the query we need to paint a blue node vi in red. If ti = 2, then we should reply to the query by printing the shortest distance from some red node to node vi.It is guaranteed that the given graph is a tree and that all queries are correct.

Output: For each second type query print the reply in a single line.


Sample Inputs:
5 4
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5

Sample Outputs:
0
3
2

Solution (Python):
class CentroidDecomposition:

    def __init__(self, g):
        self.g = g
        self.n = len(g)
        self.parent = [-1] * self.n
        self.size = [1] * self.n
        self.cdparent = [-1] * self.n
        self.cddepth = [0] * self.n
        self.cdorder = [-1] * self.n
        self.cdused = [0] * self.n
        cnt = 0
        stack = [0]
        while stack:
            v = stack.pop()
            p = self.cdparent[v]
            c = self.get_centroid(v)
            self.cdused[c] = True
            self.cdparent[c] = p
            self.cddepth[c] = self.cddepth[v]
            self.cdorder[c] = cnt
            cnt += 1
            for u in self.g[c]:
                if self.cdused[u]:
                    continue
                self.cdparent[u] = c
                self.cddepth[u] = self.cddepth[c] + 1
                stack.append(u)

    def get_centroid(self, root):
        self.parent[root] = -1
        self.size[root] = 1
        stack = [root]
        order = []
        while stack:
            v = stack.pop()
            order.append(v)
            for u in g[v]:
                if self.parent[v] == u or self.cdused[u]:
                    continue
                self.size[u] = 1
                self.parent[u] = v
                stack.append(u)
        if len(order) <= 2:
            return root
        for v in reversed(order):
            if self.parent[v] == -1:
                continue
            self.size[self.parent[v]] += self.size[v]
        total = self.size[root]
        v = root
        while True:
            for u in self.g[v]:
                if self.parent[v] == u or self.cdused[u]:
                    continue
                if self.size[u] > total // 2:
                    v = u
                    break
            else:
                return v

class HLD:

    def __init__(self, g):
        self.g = g
        self.n = len(g)
        self.parent = [-1] * self.n
        self.size = [1] * self.n
        self.head = [0] * self.n
        self.preorder = [0] * self.n
        self.k = 0
        self.depth = [0] * self.n
        for v in range(self.n):
            if self.parent[v] == -1:
                self.dfs_pre(v)
                self.dfs_hld(v)

    def dfs_pre(self, v):
        g = self.g
        stack = [v]
        order = [v]
        while stack:
            v = stack.pop()
            for u in g[v]:
                if self.parent[v] == u:
                    continue
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                stack.append(u)
                order.append(u)
        while order:
            v = order.pop()
            child_v = g[v]
            if len(child_v) and child_v[0] == self.parent[v]:
                (child_v[0], child_v[-1]) = (child_v[-1], child_v[0])
            for (i, u) in enumerate(child_v):
                if u == self.parent[v]:
                    continue
                self.size[v] += self.size[u]
                if self.size[u] > self.size[child_v[0]]:
                    (child_v[i], child_v[0]) = (child_v[0], child_v[i])

    def dfs_hld(self, v):
        stack = [v]
        while stack:
            v = stack.pop()
            self.preorder[v] = self.k
            self.k += 1
            top = self.g[v][0]
            for u in reversed(self.g[v]):
                if u == self.parent[v]:
                    continue
                if u == top:
                    self.head[u] = self.head[v]
                else:
                    self.head[u] = u
                stack.append(u)

    def for_each(self, u, v):
        while True:
            if self.preorder[u] > self.preorder[v]:
                (u, v) = (v, u)
            l = max(self.preorder[self.head[v]], self.preorder[u])
            r = self.preorder[v]
            yield (l, r)
            if self.head[u] != self.head[v]:
                v = self.parent[self.head[v]]
            else:
                return

    def for_each_edge(self, u, v):
        while True:
            if self.preorder[u] > self.preorder[v]:
                (u, v) = (v, u)
            if self.head[u] != self.head[v]:
                yield (self.preorder[self.head[v]], self.preorder[v])
                v = self.parent[self.head[v]]
            else:
                if u != v:
                    yield (self.preorder[u] + 1, self.preorder[v])
                break

    def subtree(self, v):
        l = self.preorder[v]
        r = self.preorder[v] + self.size[v]
        return (l, r)

    def lca(self, u, v):
        while True:
            if self.preorder[u] > self.preorder[v]:
                (u, v) = (v, u)
            if self.head[u] == self.head[v]:
                return u
            v = self.parent[self.head[v]]
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(n - 1):
    (a, b) = map(int, input().split())
    (a, b) = (a - 1, b - 1)
    g[a].append(b)
    g[b].append(a)
cd = CentroidDecomposition(g)
hld = HLD(g)
min_dist = [0] * n
for i in range(n):
    min_dist[i] = hld.depth[i]
for i in range(m):
    (t, v) = map(int, input().split())
    v -= 1
    if t == 1:
        cur = v
        while cur != -1:
            l = hld.lca(cur, v)
            d = hld.depth[cur] + hld.depth[v] - 2 * hld.depth[l]
            min_dist[cur] = min(min_dist[cur], d)
            cur = cd.cdparent[cur]
    else:
        ans = n
        cur = v
        while cur != -1:
            l = hld.lca(cur, v)
            d = hld.depth[cur] + hld.depth[v] - 2 * hld.depth[l]
            ans = min(ans, d + min_dist[cur])
            cur = cd.cdparent[cur]
        print(ans)

Solution (Python):
class Tree:

    def __init__(self, n):
        self.n = n
        self.tree = [[] for _ in range(n)]
        self.root = None

    def add_edge(self, u, v):
        self.tree[u].append(v)
        self.tree[v].append(u)

    def set_root(self, r=0):
        self.root = r
        self.par = [None] * self.n
        self.dep = [0] * self.n
        self.height = [0] * self.n
        self.size = [1] * self.n
        self.ord = [r]
        stack = [r]
        while stack:
            v = stack.pop()
            for adj in self.tree[v]:
                if self.par[v] == adj:
                    continue
                self.par[adj] = v
                self.dep[adj] = self.dep[v] + 1
                self.ord.append(adj)
                stack.append(adj)
        for v in self.ord[1:][::-1]:
            self.size[self.par[v]] += self.size[v]
            self.height[self.par[v]] = max(self.height[self.par[v]], self.height[v] + 1)

    def rerooting(self, op, e, merge, id):
        if self.root is None:
            self.set_root()
        dp = [e] * self.n
        lt = [id] * self.n
        rt = [id] * self.n
        inv = [id] * self.n
        for v in self.ord[::-1]:
            tl = tr = e
            for adj in self.tree[v]:
                if self.par[v] == adj:
                    continue
                lt[adj] = tl
                tl = op(tl, dp[adj])
            for adj in self.tree[v][::-1]:
                if self.par[v] == adj:
                    continue
                rt[adj] = tr
                tr = op(tr, dp[adj])
            dp[v] = tr
        for v in self.ord:
            if v == self.root:
                continue
            p = self.par[v]
            inv[v] = op(merge(lt[v], rt[v]), inv[p])
            dp[v] = op(dp[v], inv[v])
        return dp

    def euler_tour(self):
        if self.root is None:
            self.set_root()
        self.tour = []
        self.etin = [None for _ in range(self.n)]
        self.etout = [None for _ in range(self.n)]
        used = [0 for _ in range(self.n)]
        used[self.root] = 1
        stack = [self.root]
        while stack:
            v = stack.pop()
            if v >= 0:
                self.tour.append(v)
                stack.append(~v)
                if self.etin[v] is None:
                    self.etin[v] = len(self.tour) - 1
                for adj in self.tree[v]:
                    if used[adj]:
                        continue
                    used[adj] = 1
                    stack.append(adj)
            else:
                self.etout[~v] = len(self.tour)
                if ~v != self.root:
                    self.tour.append(self.par[~v])

    def heavylight_decomposition(self):
        if self.root is None:
            self.set_root()
        self.hldid = [None] * self.n
        self.hldtop = [None] * self.n
        self.hldtop[self.root] = self.root
        self.hldnxt = [None] * self.n
        self.hldrev = [None] * self.n
        stack = [self.root]
        cnt = 0
        while stack:
            v = stack.pop()
            self.hldid[v] = cnt
            self.hldrev[cnt] = v
            cnt += 1
            maxs = 0
            for adj in self.tree[v]:
                if self.par[v] == adj:
                    continue
                if maxs < self.size[adj]:
                    maxs = self.size[adj]
                    self.hldnxt[v] = adj
            for adj in self.tree[v]:
                if self.par[v] == adj or self.hldnxt[v] == adj:
                    continue
                self.hldtop[adj] = adj
                stack.append(adj)
            if self.hldnxt[v] is not None:
                self.hldtop[self.hldnxt[v]] = self.hldtop[v]
                stack.append(self.hldnxt[v])

    def lca(self, u, v):
        while True:
            if self.hldid[u] > self.hldid[v]:
                (u, v) = (v, u)
            if self.hldtop[u] != self.hldtop[v]:
                v = self.par[self.hldtop[v]]
            else:
                return u

    def dist(self, u, v):
        lca = self.lca(u, v)
        return self.dep[u] + self.dep[v] - 2 * self.dep[lca]

    def range_query(self, u, v, edge_query=False):
        while True:
            if self.hldid[u] > self.hldid[v]:
                (u, v) = (v, u)
            if self.hldtop[u] != self.hldtop[v]:
                yield (self.hldid[self.hldtop[v]], self.hldid[v] + 1)
                v = self.par[self.hldtop[v]]
            else:
                yield (self.hldid[u] + edge_query, self.hldid[v] + 1)
                return

    def subtree_query(self, u):
        return (self.hldid[u], self.hldid[u] + self.size[u])

    def _get_centroid_(self, r):
        self._par_[r] = None
        self._size_[r] = 1
        ord = [r]
        stack = [r]
        while stack:
            v = stack.pop()
            for adj in self.tree[v]:
                if self._par_[v] == adj or self.cdused[adj]:
                    continue
                self._size_[adj] = 1
                self._par_[adj] = v
                ord.append(adj)
                stack.append(adj)
        if len(ord) <= 2:
            return r
        for v in ord[1:][::-1]:
            self._size_[self._par_[v]] += self._size_[v]
        sr = self._size_[r] // 2
        v = r
        while True:
            for adj in self.tree[v]:
                if self._par_[v] == adj or self.cdused[adj]:
                    continue
                if self._size_[adj] > sr:
                    v = adj
                    break
            else:
                return v

    def centroid_decomposition(self):
        self._par_ = [None] * self.n
        self._size_ = [1] * self.n
        self.cdpar = [None] * self.n
        self.cddep = [0] * self.n
        self.cdord = [None] * self.n
        self.cdused = [0] * self.n
        cnt = 0
        stack = [0]
        while stack:
            v = stack.pop()
            p = self.cdpar[v]
            c = self._get_centroid_(v)
            self.cdused[c] = True
            self.cdpar[c] = p
            self.cddep[c] = self.cddep[v]
            self.cdord[c] = cnt
            cnt += 1
            for adj in self.tree[c]:
                if self.cdused[adj]:
                    continue
                self.cdpar[adj] = c
                self.cddep[adj] = self.cddep[c] + 1
                stack.append(adj)

    def centroid(self):
        if self.root is None:
            self.set_root()
        sr = self.size[self.root] // 2
        v = self.root
        while True:
            for adj in self.tree[v]:
                if self.par[v] == adj:
                    continue
                if self.size[adj] > sr:
                    v = adj
                    break
            else:
                return v

    def diam(self):
        if self.root is None:
            self.set_root()
        u = self.dep.index(max(self.dep))
        self.set_root(u)
        v = self.dep.index(max(self.dep))
        return (u, v)

    def get_path(self, u, v):
        if self.root != u:
            self.set_root(u)
        path = []
        while v != None:
            path.append(v)
            v = self.par[v]
        return path

    def longest_path_decomposition(self, make_ladder=True):
        assert self.root is not None
        self.lpdnxt = [None] * self.n
        self.lpdtop = [None] * self.n
        self.lpdtop[self.root] = self.root
        stack = [self.root]
        while stack:
            v = stack.pop()
            for adj in self.tree[v]:
                if self.par[v] == adj:
                    continue
                if self.height[v] == self.height[adj] + 1:
                    self.lpdnxt[v] = adj
            for adj in self.tree[v]:
                if self.par[v] == adj or self.lpdnxt[v] == adj:
                    continue
                self.lpdtop[adj] = adj
                stack.append(adj)
            if self.lpdnxt[v] is not None:
                self.lpdtop[self.lpdnxt[v]] = self.lpdtop[v]
                stack.append(self.lpdnxt[v])
        if make_ladder:
            self._make_ladder_()

    def _make_ladder_(self):
        self.ladder = [[] for _ in range(self.n)]
        for v in range(self.n):
            if self.lpdtop[v] != v:
                continue
            to = v
            path = []
            while to is not None:
                path.append(to)
                to = self.lpdnxt[to]
            p = self.par[v]
            self.ladder[v] = path[::-1]
            for i in range(len(path)):
                self.ladder[v].append(p)
                if p is None:
                    break
                p = self.par[p]

    def level_ancestor(self, v, k):
        while v is not None:
            id = self.height[v]
            h = self.lpdtop[v]
            if len(self.ladder[h]) > k + id:
                return self.ladder[h][k + id]
            v = self.ladder[h][-1]
            k -= len(self.ladder[h]) - id - 1
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, Q) = map(int, input().split())
t = Tree(N)
for _ in range(N - 1):
    (u, v) = map(int, input().split())
    t.add_edge(u - 1, v - 1)
t.heavylight_decomposition()
t.centroid_decomposition()
min_dist = [N] * N
res = []

def query_1(v):
    cur = v
    while cur is not None:
        min_dist[cur] = min(min_dist[cur], t.dist(cur, v))
        cur = t.cdpar[cur]

def query_2(v):
    ret = N
    cur = v
    while cur is not None:
        ret = min(ret, t.dist(cur, v) + min_dist[cur])
        cur = t.cdpar[cur]
    return ret
query_1(0)
for _ in range(Q):
    (q, v) = map(int, input().split())
    if q == 1:
        query_1(v - 1)
    else:
        res.append(query_2(v - 1))
print('\n'.join(map(str, res)))

Solution (Python):
class CentroidDecomposition:

    def __init__(self, g):
        self.g = g
        self.n = len(g)
        self.parent = [-1] * self.n
        self.size = [1] * self.n
        self.cdparent = [-1] * self.n
        self.cddepth = [0] * self.n
        self.cdorder = [-1] * self.n
        self.cdused = [0] * self.n
        cnt = 0
        stack = [0]
        while stack:
            v = stack.pop()
            p = self.cdparent[v]
            c = self.get_centroid(v)
            self.cdused[c] = True
            self.cdparent[c] = p
            self.cddepth[c] = self.cddepth[v]
            self.cdorder[c] = cnt
            cnt += 1
            for u in self.g[c]:
                if self.cdused[u]:
                    continue
                self.cdparent[u] = c
                self.cddepth[u] = self.cddepth[c] + 1
                stack.append(u)

    def get_centroid(self, root):
        self.parent[root] = -1
        self.size[root] = 1
        stack = [root]
        order = []
        while stack:
            v = stack.pop()
            order.append(v)
            for u in g[v]:
                if self.parent[v] == u or self.cdused[u]:
                    continue
                self.size[u] = 1
                self.parent[u] = v
                stack.append(u)
        if len(order) <= 2:
            return root
        for v in reversed(order):
            if self.parent[v] == -1:
                continue
            self.size[self.parent[v]] += self.size[v]
        total = self.size[root]
        v = root
        while True:
            for u in self.g[v]:
                if self.parent[v] == u or self.cdused[u]:
                    continue
                if self.size[u] > total // 2:
                    v = u
                    break
            else:
                return v

class SegTree:

    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num = 2 ** (self.n - 1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.seg = [ide_ele] * 2 * self.num
        for i in range(self.n):
            self.seg[i + self.num] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.seg[k] = x
        while k:
            k = k >> 1
            self.seg[k] = self.segfunc(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, l, r):
        if r <= l:
            return self.ide_ele
        l += self.num
        r += self.num
        res = self.ide_ele
        while l < r:
            if r & 1:
                r -= 1
                res = self.segfunc(res, self.seg[r])
            if l & 1:
                res = self.segfunc(res, self.seg[l])
                l += 1
            l = l >> 1
            r = r >> 1
        return res

def segfunc(x, y):
    if x <= y:
        return x
    else:
        return y
ide_ele = 10 ** 18

class LCA:

    def __init__(self, g, root):
        self.n = len(g)
        self.root = root
        s = [self.root]
        self.parent = [-1] * self.n
        self.child = [[] for _ in range(self.n)]
        visit = [-1] * self.n
        visit[self.root] = 0
        while s:
            v = s.pop()
            for u in g[v]:
                if visit[u] == -1:
                    self.parent[u] = v
                    self.child[v].append(u)
                    visit[u] = 0
                    s.append(u)
        tank = [self.root]
        self.eulerTour = []
        self.left = [0] * self.n
        self.right = [-1] * self.n
        self.depth = [-1] * self.n
        eulerNum = -1
        de = -1
        while tank:
            v = tank.pop()
            if v >= 0:
                eulerNum += 1
                self.eulerTour.append(v)
                self.left[v] = eulerNum
                self.right[v] = eulerNum
                tank.append(~v)
                de += 1
                self.depth[v] = de
                for u in self.child[v]:
                    tank.append(u)
            else:
                de -= 1
                if ~v != self.root:
                    self.eulerTour.append(self.parent[~v])
                    eulerNum += 1
                    self.right[self.parent[~v]] = eulerNum
        A = [0] * (2 * self.n - 1)
        for (i, e) in enumerate(self.eulerTour):
            A[i] = self.depth[e] * (2 * self.n - 1) + i
        self.seg = SegTree(A, ide_ele, segfunc)

    def getLCA(self, u, v):
        p = min(self.left[u], self.left[v])
        q = max(self.right[u], self.left[v]) + 1
        m = self.seg.query(p, q)
        return self.eulerTour[m % (2 * self.n - 1)]
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(n - 1):
    (a, b) = map(int, input().split())
    (a, b) = (a - 1, b - 1)
    g[a].append(b)
    g[b].append(a)
cd = CentroidDecomposition(g)
lca = LCA(g, 0)
min_dist = [0] * n
for i in range(n):
    min_dist[i] = lca.depth[i]
for i in range(m):
    (t, v) = map(int, input().split())
    v -= 1
    if t == 1:
        cur = v
        while cur != -1:
            l = lca.getLCA(cur, v)
            d = lca.depth[cur] + lca.depth[v] - 2 * lca.depth[l]
            min_dist[cur] = min(min_dist[cur], d)
            cur = cd.cdparent[cur]
    else:
        ans = n
        cur = v
        while cur != -1:
            l = lca.getLCA(cur, v)
            d = lca.depth[cur] + lca.depth[v] - 2 * lca.depth[l]
            ans = min(ans, d + min_dist[cur])
            cur = cd.cdparent[cur]
        print(ans)