Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
用RMQ老是RE 树链剖分水一发#include<iostream> #include<algorithm> using namespace std; #define maxn 10010 int k = 1; int in[maxn],head[maxn],num[maxn], son[maxn], fa[maxn], top[maxn], deep[maxn]; struct edge { int v, next; }Edge[maxn << 1]; void addedge(int a, int b) { Edge[k].v = b; Edge[k].next = head[a]; head[a] = k++; } void dfs1(int pos, int pre, int dep) { fa[pos] = pre; num[pos] = 1; deep[pos] = dep; for (int i = head[pos]; i; i = Edge[i].next) { int v = Edge[i].v; if (v != pre) { dfs1(v, pos, dep + 1); num[pos] += num[v]; if (son[pos] == -1 || num[son[pos]] < num[v]) son[pos] = v; } } } void dfs2(int pos, int pre, int Top) { top[pos] = Top; if (son[pos] == -1) return; dfs2(son[pos], pos, Top); for (int i = head[pos]; i; i = Edge[i].next) { int v = Edge[i].v; if (v != pre&&v != son[pos]) dfs2(v, pos, v); } } int Query(int a, int b) { int f1 = top[a], f2 = top[b]; while (f1 != f2) { if (deep[f1] < deep[f2]) { swap(a, b); swap(f1, f2); } a = fa[f1], f1 = top[a]; } if (deep[a] < deep[b]) swap(a, b); return b; } int main() { int t; cin >> t; while (t--) { k = 1; memset(in, 0, sizeof(in)); memset(son, -1, sizeof(son)); memset(head, 0, sizeof(head)); int n, a, b; cin >> n; for (int i = 1; i < n; i++) { cin >> a >> b; in[b]++; addedge(a, b); addedge(b, a); } int i = 1; for (; i <= n; i++) if (!in[i]) break; dfs1(i, -1, 1); dfs2(i, -1, i); cin >> a >> b; cout <<Query(a,b) << endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator