3676719_ac_1219ms_4856k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define WHITE 0
#define BLACK 1
#define maxn 40001
#define maxm 20001
using namespace std;

int n, m;
int color[maxn];
int p[maxn], rank[maxn];
int ancestor[maxn];
int father[maxn];
typedef pair <int, int> type;
vector <type> tree[maxn];
int st[maxn], ed[maxn];
struct node
{
	int u, v, id, dis;
	bool operator < (const node &that)	const
	{
		return u < that.u;
	}
};

node query[maxm];
int dis[maxn];

void MAKE_SET(int x)
{
	p[x] = x;
	rank[x] = x;
}

int FIND_SET(int x)
{
	if (x!=p[x])
		return p[x] = FIND_SET(p[x]);
	else
		return p[x];
}

void LINK(int x,int y)
{
	if (rank[x] > rank[y])
	{
		p[y] = x;
	}
	else
	{
		p[x] = y;
		if (rank[x] == rank[y])
		{
			rank[y]++;
		}
	}
}

void UNION(int x,int y)
{
	LINK(FIND_SET(x),FIND_SET(y));
}

void LCA(int u)
{
	int i, v;

	MAKE_SET(u);
	ancestor[FIND_SET(u)] = u;
	for (i = 0; i < tree[u].size(); i++)
	{
		v = tree[u][i].first;
		if (father[u]==v)
		{
			continue;
		}
		LCA(v);
		UNION(u,v);
		ancestor[FIND_SET(u)] = u;
	}
	color[u] = BLACK;
	if (st[u]!=-1)
	{
		for (i = st[u]; i <= ed[u]; i++)
		{
			if (color[query[i].v]==WHITE)
			{
				continue;
			}
			int t;
			query[i].dis = dis[u]+dis[query[i].v]-dis[t = ancestor[FIND_SET(query[i].v)]]*2;
		}
	}
}

void input()
{
	int i; 
	int v, u, w;

	scanf("%d%*s",&n);
	for (i = 1; i < n; i++)
	{
		scanf("%d%d%d%*s",&u,&v,&w);
		u--;v--;
		tree[u].push_back(make_pair(v,w));
		tree[v].push_back(make_pair(u,w));
	}
	memset(color,WHITE,sizeof(color));
	scanf("%d",&m);
	for (i = 0; i < m; i++)
	{
		scanf("%d%d",&query[i].u,&query[i].v);
		query[i].u--;query[i].v--;
		query[i+m].u = query[i].v;
		query[i+m].v = query[i].u;
		query[i].dis = query[i+m].dis = -1;
		query[i].id = query[i+m].id = i;
	}
	m <<= 1;
	sort(query,query+m);
	memset(st,-1,sizeof(st));
	for (i = 0; i < m; i++)
	{
		ed[query[i].u] = i;
	}
	for (i = m-1; i >= 0; i--)
	{
		st[query[i].u] = i;
	}
}

void bfs()
{
	int i, u;
	queue <int> que;

	que.push(0);
	dis[0] = 0;
	father[0] = -1;
	while (!que.empty())
	{
		u = que.front();
		que.pop();
		for (i = 0; i < tree[u].size(); i++)
		{
			if (father[u]==tree[u][i].first)
			{
				continue;
			}
			father[tree[u][i].first] = u;
			dis[tree[u][i].first] = dis[u] + tree[u][i].second;
			que.push(tree[u][i].first);
		}
	}
}

int ans[maxm/2];

void print()
{
	int i;

	for (i = 0; i < m; i++)
	{
		if (query[i].dis!=-1)
		{
			ans[query[i].id] = query[i].dis;
		}
	}
	for (i = 0; i < m/2; i++)
	{
		printf("%d\n",ans[i]);
	}
}

int main()
{
	input();
	bfs();
	LCA(0);
	print();
	return 0;
}