Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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];

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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator