Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 用RMQ老是RE 树链剖分水一发

Posted by marszed at 2017-05-16 21:09:07 on Problem 1330
```#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];

{
Edge[k].v = b;
}

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));
int n, a, b;
cin >> n;
for (int i = 1; i < n; i++)
{
cin >> a >> b;
in[b]++;
}
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: