Hướng dẫn giải của VM 08 Bài 15 - Truy vấn trên cây
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <cstdio> #include <vector> using namespace std; const int N = 100100; struct segmentTree { int low, high, mid, black; segmentTree *L, *R; segmentTree() {} segmentTree(int _low, int _high) { low = _low; high = _high; mid = (low + high) / 2; black = -1; if (low < high) { L = new segmentTree(low, mid); R = new segmentTree(mid + 1, high); } } void update(int x, int v) { if (low == high) { if (black < 0) black = v; else black = -1; } else { if (x <= mid) L -> update(x, v); else R -> update(x, v); if (L -> black < 0) black = R -> black; else black = L -> black; } } int get(int x, int y) { if (low == x && high == y) return black; int u = -1; if (x <= mid) u = L -> get(x, min(y, mid)); if (u > 0) return u; if (mid < y) return R -> get(max(x, mid + 1), y); return -1; } }; int n, par[N], s[N], heavyDown[N], heavyUp[N]; int sizeChain[N], idChain[N], posChain[N], numChain, firstOnChain[N]; vector <int> a[N]; vector <segmentTree> tree; void visit(int x) { s[x] = 1; for (int i = 0; i < int(a[x].size()); i++) { int y = a[x][i]; if (y != par[x]) { par[y] = x; visit(y); s[x] += s[y]; } } for (int i = 0; i < int(a[x].size()); i++) { int y = a[x][i]; if (y != par[x] && s[y] * 2 >= s[x]) heavyDown[x] = y, heavyUp[y] = 1; } } void initHeavyLight() { visit(1); for (int i = 1; i <= n; i++) { int x = i; if (heavyUp[x]) continue; firstOnChain[numChain] = x; while (x) { idChain[x] = numChain; posChain[x] = sizeChain[numChain]++; x = heavyDown[x]; } tree.push_back(segmentTree(0, sizeChain[numChain++] - 1)); } } int main() { int Q, x, y, type; cin >> n >> Q; for (int i = 1; i < n; i++) { scanf("%d%d", &x, &y); a[x].push_back(y); a[y].push_back(x); } initHeavyLight(); while (Q--) { scanf("%d%d", &type, &x); if (type) { int ans = -1; while (x) { int u = tree[idChain[x]].get(0, posChain[x]); if (u > 0) ans = u; x = par[firstOnChain[idChain[x]]]; } printf("%d\n", ans); } else tree[idChain[x]].update(posChain[x], x); } }
Code mẫu của ladpro98
//by ladpro98 //Heavy - Light Decomposition #include <bits/stdc++.h> #define SetLength(a, n, t) free(a), a=(t*) calloc(n, sizeof(t)) const int N = 100005; const int oo = 2000000000; const int C = N; using namespace std; int n, q; vector<int> a[N]; int Size[N], par[N], chainHead[N], chainNo, chainPos[N], chainID[N], chainSize[N]; struct segment_tree { int n; int *tree; int *node; void init(int _n); void Upd(int k, int l, int r, int x); void Upd(int x) {Upd(1, 1, n, x);} int Get(int k, int l, int r, int i, int j); int Get(int i, int j) {return Get(1, 1, n, i, j);} }; segment_tree t[C]; void segment_tree :: init(int _n) { n = _n; SetLength(tree, 4 * n, int); SetLength(node, n + 2, int); for(int i=1; i<=4 * n; i++) tree[i] = oo; } void segment_tree :: Upd(int k, int l, int r, int x) { if (l > r || r < x || x < l) return; if (l == r) { if (tree[k] == oo) tree[k] = l; else tree[k] = oo; return; } int mid = (l + r) >> 1; Upd(k + k, l, mid, x); Upd(k + k + 1, mid + 1, r, x); tree[k] = min(tree[k + k], tree[k + k + 1]); } int segment_tree :: Get(int k, int l, int r, int i, int j) { if (l > r || r < i || j < l) return oo; if (i <= l && r <= j) return tree[k]; int mid = (l + r) >> 1; return min(Get(k+k, l, mid, i, j), Get(k+k+1, mid + 1, r, i, j)); } void Enter() { scanf("%d %d", &n, &q); int i, u, v; for(i=1; i<n; i++) { scanf("%d %d", &u, &v); a[u].push_back(v); a[v].push_back(u); } } void DFS(int u) { int i, v; Size[u] = 1; for(i=0; i<a[u].size(); i++) { v = a[u][i]; if (v != par[u]) { par[v] = u; DFS(v); Size[u] += Size[v]; } } } void HLD(int u) { if (chainHead[chainNo] == -1) chainHead[chainNo] = u; chainID[u] = chainNo; chainPos[u] = ++chainSize[chainNo]; int ind = -1, ma = -1; for(int i=0; i<a[u].size(); i++) if (a[u][i] != par[u]) if (ma < Size[a[u][i]]) { ma = Size[a[u][i]]; ind = i; } if (ind >=0 ) HLD(a[u][ind]); for(int i=0; i<a[u].size(); i++) if (a[u][i] != par[u]) { if (i != ind) { chainNo++; HLD(a[u][i]); } } } void init_Helper() { for(int i=1; i<C; i++) chainHead[i] = -1; chainNo = 1; DFS(1); HLD(1); for(int i=1; i<=chainNo; i++) t[i].init(chainSize[i]); for(int i=1; i<=n; i++) t[chainID[i]].node[chainPos[i]] = i; } int query(int u, int v) { int res = oo, pos = oo; while (1) { if (chainID[u] == chainID[v]) { pos = t[chainID[u]].Get(1, chainPos[u]); if (pos < oo) res = t[chainID[u]].node[pos]; break; } pos = t[chainID[u]].Get(1, chainPos[u]); if (pos < oo) res = t[chainID[u]].node[pos]; u = par[chainHead[chainID[u]]]; } return res; } int main() { Enter(); init_Helper(); int kind, u, r; while (q--) { scanf("%d %d", &kind, &u); if (kind == 0) t[chainID[u]].Upd(chainPos[u]); else { r = query(u, 1); if (r < oo) printf("%d\n", r); else printf("-1\n"); } } return 0; }
Code mẫu của RR
//Written by Nguyen Thanh Trung {$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=100001; type list=^node; node=record u:longint; next:list; end; var f1,f2:text; n,q,count:longint; ke:array[1..MAXN] of list; num,sc,color:array[1..MAXN] of longint; trace,d,head,size:array[1..MAXN] of longint; first:array[1..MAXN] of array of longint; procedure openF; inline; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; inline; begin close(f1); close(f2); end; procedure add(u:longint; var a:list); inline; var p:list; begin new(p); p^.u:=u; p^.next:=a; a:=p; end; function cal(n:longint):longint; inline; var temp:longint; begin temp:=trunc(ln(n)/ln(2)+2); cal:=1<<temp+2; end; procedure inp; inline; var i,u,v:longint; begin read(f1,n,q); for i:=1 to n-1 do begin read(f1,u,v); add(u,ke[v]); add(v,ke[u]); end; end; procedure dfs1(u:longint); inline; var v:longint; p:list; begin sc[u]:=1; p:=ke[u]; while p<>nil do begin v:=p^.u; p:=p^.next; if sc[v]>0 then continue; dfs1(v); inc(sc[u],sc[v]); end; end; procedure dfs2(u:longint); inline; var v,next,ln:longint; p:list; begin inc(count); num[u]:=count; ln:=-1; next:=0; p:=ke[u]; while p<>nil do begin v:=p^.u; p:=p^.next; if head[v]>0 then continue; if sc[v]>ln then begin ln:=sc[v]; next:=v; end; end; if next=0 then exit; head[next]:=head[u]; d[next]:=d[u]+1; inc(size[head[u]]); dfs2(next); p:=ke[u]; while p<>nil do begin v:=p^.u; p:=p^.next; if head[v]>0 then continue; trace[v]:=u; head[v]:=v; size[v]:=1; d[v]:=1; dfs2(v); end; end; procedure solve; inline; var i:longint; begin count:=0; head[1]:=1; d[1]:=1; size[1]:=1; dfs1(1); dfs2(1); for i:=1 to n do if head[i]=i then setlength(first[i],cal(size[i])); end; procedure update(tree,u,k:longint); procedure visit(i,l,r:longint); inline; var mid:longint; begin if l>r then exit; if (d[u]<l) or (r<d[u]) then exit; if (l=r) then begin if k=0 then first[tree,i]:=0 else first[tree,i]:=u; exit; end; mid:=(l+r)>>1; visit(i<<1,l,mid); visit(i<<1+1,mid+1,r); if first[tree,i<<1]>0 then first[tree,i]:=first[tree,i<<1] else first[tree,i]:=first[tree,i<<1+1]; end; begin visit(1,1,size[tree]); end; function get(tree,u:longint):longint; inline; var kq:longint; procedure visit(i,l,r:longint); inline; var mid:longint; begin if l>r then exit; if u<l then exit; if u>=r then begin if first[tree,i]>0 then kq:=first[tree,i]; exit; end; mid:=(l+r)>>1; visit(i<<1,l,mid); if kq=0 then visit(i<<1+1,mid+1,r); end; begin kq:=0; visit(1,1,size[tree]); get:=kq; end; function query(u:longint):longint; inline; var h,x,kq:longint; begin h:=head[u]; if h>1 then begin kq:=query(trace[h]); if kq=0 then kq:=get(h,d[u]); end else kq:=get(h,d[u]); query:=kq; end; procedure ans; var i,yc,u,kq:longint; begin for i:=1 to q do begin read(f1,yc,u); if yc=0 then begin color[u]:=1-color[u]; update(head[u],u,color[u]); end else begin kq:=query(u); if kq=0 then kq:=-1; writeln(f2,kq); end; end; end; begin openF; inp; solve; ans; closeF; end.
Code mẫu của ll931110
//This program using heavy-light decomposition method, which is known with the name Dynamic Tree {$MODE DELPHI,R+,Q+} program QTREE3; const input = ''; output = ''; maxn = 100000; type pnode = ^tnode; tnode = record val: integer; link: pnode; end; var fi,fo: text; n,q,dyna: integer; //dyna: number of node in dynamic tree tree: array[1..4 * maxn] of integer; stat: array[1..maxn] of boolean; a: array[1..maxn] of pnode; lab,pos,size,maxnode: array[1..maxn] of integer; pr,st,fin: array[1..maxn] of integer; u1,u2,k: integer; //Use for queries in Interval Tree ch: boolean; tk,res: integer; procedure openfile; begin assign(fi, input); reset(fi); assign(fo, output); rewrite(fo); end; procedure add(u,v: integer); var p: pnode; begin new(p); p^.val := v; p^.link := a[u]; a[u] := p; end; procedure init; var i,u,v: integer; begin readln(fi, n, q); for i := 1 to n do a[i] := nil; for i := 1 to n - 1 do begin readln(fi, u, v); add(u,v); add(v,u); end; end; procedure prepare; begin fillchar(pr, sizeof(pr), 0); fillchar(pos, sizeof(pos), 0); end; //Dynamic tree construction procedure DFS(u: integer); var p: pnode; max,v: integer; begin p := a[u]; size[u] := 1; max := 0; while p <> nil do begin v := p^.val; if v <> pr[u] then begin pr[v] := u; DFS(v); size[u] := size[u] + size[v]; if size[v] > max then begin max := size[v]; maxnode[u] := v; end; end; p := p^.link; end; end; procedure struct(u: integer); var p: pnode; v,endnode: integer; begin p := a[u]; if (pos[u] = 0) and (p <> nil) then begin inc(dyna); pos[u] := dyna; lab[dyna] := u; st[u] := u; endnode := u; v := maxnode[u]; while v <> 0 do begin inc(dyna); pos[v] := dyna; lab[dyna] := v; st[v] := u; if maxnode[v] = 0 then endnode := v; v := maxnode[v]; end; v := u; while v <> 0 do begin fin[v] := endnode; v := maxnode[v]; end; end; while p <> nil do begin v := p^.val; if v <> pr[u] then struct(v); p := p^.link; end; end; //End of Dynamic tree construction procedure upIT(i,low,high: integer); var mid: integer; begin if low = high then begin if ch then tree[i] := low else tree[i] := -1; exit; end; mid := (low + high) div 2; if k <= mid then upIT(2 * i,low,mid) else upIT(2 * i + 1,mid + 1,high); if tree[2 * i] = -1 then tree[i] := tree[2 * i + 1] else tree[i] := tree[2 * i]; end; procedure calc(i,low,high: integer); var mid: integer; begin if (u2 < low) or (high < u1) then exit; if (u1 <= low) and (high <= u2) then begin if (tree[i] <> -1) and ((tk = -1) or (tk > tree[i])) then tk := tree[i]; exit; end; mid := (low + high) div 2; calc(2 * i,low,mid); calc(2 * i + 1,mid + 1,high); end; procedure update(y: integer); begin k := pos[y]; stat[y] := not stat[y]; ch := stat[y]; if pos[y] <> 0 then upIT(1,1,dyna); end; procedure ask(y: integer); var tmp: integer; begin if y = 0 then exit; if stat[y] then tmp := y else tmp := -1; if tmp <> -1 then res := tmp; if (y = st[y]) or (pos[y] = 0) then ask(pr[y]) else begin u1 := pos[st[y]]; u2 := pos[y]; tk := -1; calc(1,1,dyna); if tk <> -1 then res := lab[tk]; ask(pr[st[y]]); end; end; procedure query; var i,x,y: integer; begin DFS(1); dyna := 0; struct(1); for i := 1 to 4 * dyna do tree[i] := -1; fillchar(stat, sizeof(stat), false); for i := 1 to q do begin readln(fi, x, y); if x = 0 then update(y) else begin res := -1; ask(y); writeln(fo, res); end; end; end; procedure closefile; begin close(fo); close(fi); end; begin openfile; init; prepare; query; closefile; end.
Bình luận