Author : Dipu Kumar Mohanto
CSE, Batch - 6
BRUR.
Problem Statement : 12424 - Answering Queries on a Tree
Source : UVA Online Judge
Category : Graph Theory
Algorithm : Heavy Light Decomposition, Segment Tree
Verdict : Accepted
- #include <bits/stdc++.h>
-
- using namespace std;
-
- static const int maxn = 1e5 + 5;
- static const int logn = 19;
-
- int chainNo, chainHead[maxn], chainInd[maxn], chainPos[maxn], chainSize[maxn],
- baseArray[maxn], posBase[maxn], ptr, depth[maxn], father[maxn][logn],
- subTreeSize[maxn], startnode[maxn], endNode[maxn], nodeInd[maxn],
- S, E, nodeColor[maxn];
-
- struct node
- {
- int v,
- e;
- node() {}
- node(int v, int e) : v(v), e(e) {}
- };
-
- vector <node> graph[maxn];
-
- void dfs(int u = 1, int p = -1)
- {
- for (int i = 1; i < logn; i++) father[u][i] = father[father[u][i-1]][i-1];
- subTreeSize[u] = 1;
- for (node g : graph[u])
- {
- int v = g.v;
- int e = g.e;
- if (v == p) continue;
- depth[v] = depth[u] + 1;
- father[v][0] = u;
- startnode[e] = u;
- endNode[e] = v;
- dfs(v, u);
- subTreeSize[u] += subTreeSize[v];
- }
- }
-
- int findLCA(int u, int v)
- {
- if (depth[u] < depth[v]) swap(u, v);
- for (int i = logn-1; i >= 0; i--)
- {
- if (depth[father[u][i]] >= depth[v])
- {
- u = father[u][i];
- }
- }
- if (u == v) return u;
- for (int i = logn-1; i >= 0; i--)
- {
- if (father[u][i] != father[v][i])
- {
- u = father[u][i];
- v = father[v][i];
- }
- }
- return father[u][0];
- }
-
- void hld(int u = 1, int p = -1)
- {
- if (chainHead[chainNo] == -1) chainHead[chainNo] = u;
- chainInd[u] = chainNo;
- ptr++;
- baseArray[ptr] = nodeColor[u];
- posBase[u] = ptr;
- int bigChild = -1;
- int mx = -1;
- for (node g : graph[u])
- {
- int v = g.v;
- if (v == p) continue;
- if (subTreeSize[v] > mx) mx = subTreeSize[v], bigChild = v;
- }
- if (bigChild != -1) hld(bigChild, u);
- for (node g : graph[u])
- {
- int v = g.v;
- if (v == p) continue;
- if (bigChild != v)
- {
- chainNo++;
- hld(v, u);
- }
- }
- }
-
- struct segmentTree
- {
- int color[11];
- void assignLeaf(int val)
- {
- fill(begin(color), end(color), 0);
- assert(1 <= val && val <= 10);
- color[val]++;
- }
- void marge(segmentTree &L, segmentTree &R)
- {
- for (int i = 1; i <= 10; i++) color[i] = L.color[i] + R.color[i];
- }
- int maxTimes()
- {
- int maxc = -1;
- for (int i = 1; i <= 10; i++) maxc = max(maxc, color[i]);
- }
- } Tree[maxn << 2];
-
- void build(int node, int a, int b)
- {
- if (a == b)
- {
- Tree[node].assignLeaf(baseArray[a]);
- return;
- }
- int lft = node << 1;
- int rgt = lft | 1;
- int mid = (a + b) >> 1;
- build(lft, a, mid);
- build(rgt, mid+1, b);
- Tree[node].marge(Tree[lft], Tree[rgt]);
- }
-
- void update(int node, int a, int b, int pos, int value)
- {
- if (a > b || a > pos || b < pos) return;
- if (a >= pos && b <= pos)
- {
- Tree[node].assignLeaf(value);
- return;
- }
- int lft = node << 1;
- int rgt = lft | 1;
- int mid = (a + b) >> 1;
- update(lft, a, mid, pos, value);
- update(rgt, mid+1, b, pos, value);
- Tree[node].marge(Tree[lft], Tree[rgt]);
- }
-
- segmentTree query(int node, int a, int b, int i, int j)
- {
- if (a > b || a > j || b < i)
- {
- segmentTree nul;
- fill(begin(nul.color), end(nul.color), 0);
- return nul;
- }
- if (a >= i && b <= j) return Tree[node];
- int lft = node << 1;
- int rgt = lft | 1;
- int mid = (a + b) >> 1;
- segmentTree p1, p2, res;
- p1 = query(lft, a, mid, i, j);
- p2 = query(rgt, mid+1, b, i, j);
- res.marge(p1, p2);
- return res;
- }
-
- void change_node_color(int node, int value)
- {
- int pos = posBase[node];
- baseArray[pos] = value;
- update(1, S, E, pos, value);
- }
-
- int qColor[11];
-
- void query_UP(int u, int v)
- {
- int uChian,
- vChain = chainInd[v];
- while (true)
- {
- uChian = chainInd[u];
- if (uChian == vChain)
- {
- int l = posBase[v];
- int r = posBase[u];
- if (l > r) break;
- segmentTree q = query(1, S, E, l, r);
- for (int i = 1; i <= 10; i++) qColor[i] += q.color[i];
- break;
- }
- int l = posBase[chainHead[uChian]];
- int r = posBase[u];
- segmentTree q = query(1, S, E, l, r);
- for (int i = 1; i <= 10; i++) qColor[i] += q.color[i];
- u = father[chainHead[uChian]][0];
- }
- }
-
- int query_hld(int u, int v)
- {
- if (u == v) return 1;
- int lca = findLCA(u, v);
- fill(begin(qColor), end(qColor), 0);
- if (u != lca) query_UP(u, lca);
- if (v != lca) query_UP(v, lca);
- if (u != lca && v != lca)
- {
- qColor[baseArray[posBase[lca]]]--;
- }
- int maxc = 0;
- for (int i = 1; i <= 10; i++)
- {
- if (qColor[i] > maxc) maxc = qColor[i];
- }
- return maxc;
- }
-
-
- void initialize()
- {
- ptr = 0;
- chainNo = 0;
- for (int i = 0; i < maxn; i++)
- {
- graph[i].clear();
- subTreeSize[i] = 0;
- chainHead[i] = -1;
- chainInd[i] = 0;
- depth[i] = 0;
- baseArray[i] = 0;
- posBase[i] = 0;
- for (int j = 0; j < logn; j++) father[i][j] = 0;
- }
- }
-
- int main()
- {
-
-
- int tc;
- scanf("%d", &tc);
- for (int tcase = 1; tcase <= tc; tcase++)
- {
- initialize();
- int tnode, tquery;
- scanf("%d %d", &tnode, &tquery);
- for (int i = 1; i <= tnode; i++) scanf("%d", nodeColor+i);
- for (int e = 1; e < tnode; e++)
- {
- int u, v;
- scanf("%d %d", &u, &v);
- graph[u].push_back({v, e});
- graph[v].push_back({u, e});
- }
- int root = 1;
- depth[root] = 1;
- dfs();
- hld();
- S = 1;
- E = ptr;
- build(1, S, E);
- while (tquery--)
- {
- int type, u, v;
- scanf("%d %d %d", &type, &u, &v);
- if (type == 0)
- {
- change_node_color(u, v);
- }
- else
- {
- int maxc = query_hld(u, v);
- printf("%d\n", maxc);
- }
- }
- }
- }
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.