【BZOJ】1602: [Usaco2008 Oct]牧场行走（lca）

http://www.lydsy.com/JudgeOnline/problem.php?id=1602

一开始以为直接暴力最短路，但是n<=1000, q<=1000可能会tle。

显然我没有看到树的性质，树边只有n-1，且一个点一定能到达另一个点

所以我们求出lca，然后记录从根到每个点的距离，然后答案就是d[u]+d[v]-2*d[lca(u, v)]

然后blabla就出来了

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int N=1002;

int lca[N], d[N], fa[N], p[N], ihead[N], vis[N], cnt, n, U[N], V[N];

vector<pair<int, int> > q[N];

struct ED { int to, next, w; } e[N<<1];

void add(int u, int v, int w) {

	e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v; e[cnt].w=w;

	e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u; e[cnt].w=w;

}

const int ifind(const int &x) { return x==p[x]?x:p[x]=ifind(p[x]); }

void tarjan(const int &x) {

	p[x]=x;

	for(int i=ihead[x]; i; i=e[i].next) if(e[i].to!=fa[x]) {

		fa[e[i].to]=x; tarjan(e[i].to); p[e[i].to]=x;

	}

	vis[x]=1;

	int t=q[x].size();

	rep(i, t) if(vis[q[x][i].first]) lca[q[x][i].second]=ifind(q[x][i].first);

}

void dfs(const int &x, const int &sum) {

	d[x]=sum;

	for(int i=ihead[x]; i; i=e[i].next) if(e[i].to!=fa[x]) dfs(e[i].to, sum+e[i].w);

}

int main() {

	read(n); int cs=getint();

	int u, v, w;

	rep(i, n-1) {

		read(u); read(v); read(w);

		add(u, v, w);

	}

	for1(i, 1, cs) {

		read(u); read(v);

		U[i]=u; V[i]=v;

		q[u].push_back(pair<int, int> (v, i));

		q[v].push_back(pair<int, int> (u, i));

	}

	tarjan(n>>1); dfs(n>>1, 0);

	for1(i, 1, cs) {

		u=U[i], v=V[i];

		int lc=lca[i];

		printf("%d\n", d[u]+d[v]-(d[lc]<<1));

	}

	return 0;

}

Description

N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。这n块土地被n-1条边连接。奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。

Input

*第一行：两个被空格隔开的整数：N和Q *第二行到第n行：第i+1行有两个被空格隔开的整数：AI，BI，LI *第n+1行到n+Q行：每一行有两个空格隔开的整数：P1，P2，表示两头奶牛的编号。

Output

*第1行到第Q行：每行输出一个数，表示那两头奶牛之间的距离。

Sample Input

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

Sample Output

2
7

HINT

Source

资格赛

巴特西