hdu6115 Factory(lca)

2017年08月15日 13点热度 0人点赞 0条评论

Factory

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 413    Accepted Submission(s): 145


Problem Description
我们将A省简化为由N个城市组成,某些城市之间存在双向道路,而且A省的交通有一个特点就是任意两个城市之间都能通过道路相互到达,且在不重复经过城市的情况下任意两个城市之间的到达方案都是唯一的。聪明的你一定已经发现,这些城市构成了树这样一个结构。

现在百度陆续开了许许多多的子公司。每家子公司又会在各城市中不断兴建属于该子公司的办公室。

由于各个子公司之间经常有资源的流动,所以公司员工常常想知道,两家子公司间的最小距离。
我们可以把子公司看成一个由办公室组成的集合。那么两个子公司A和B的最小距离定义为min(dist(x,y))(x∈A,y∈B)。其中dist(x,y)表示两个办公室之间的最短路径长度。

现在共有Q个询问,每次询问分别在两个子公司间的最小距离。

 


Input
第一行一个正整数T,表示数据组数。

对于每组数据:

第一行两个正整数N和M。城市编号为1至N,子公司编号为1至M。

接下来N-1行给定所有道路的两端城市编号和道路长度。

接下来M行,依次按编号顺序给出各子公司办公室所在位置,每行第一个整数G,表示办公室数,接下来G个数为办公室所在位置。

接下来一个整数Q,表示询问数。

接下来Q行,每行两个正整数a,b(a不等于b),表示询问的两个子公司。

【数据范围】

0<=边权<=100 1<=N,M,Q,工厂总数<=100000

 


Output
对于每个询问,输出一行,表示答案。
 


Sample Input

1
3 3
1 2 1
2 3 1
2 1 1
2 2 3
2 1 3
3
1 2
2 3
1 3
 


Sample Output

1
0
0

#include
#include
#include
using namespace std;
const int mx=100000+10;
struct edge {
	int to,w;
};
vector a[mx];
vector v[mx];
int n,m,pos,f[mx][25],deep[mx],ans=0,dep[mx];
void dfs(int cur,int fa,int d) {
	deep[cur]=d;
	f[cur][0]=fa;
	for(int i=1; i<22; i++)
		f[cur][i]=f[f[cur][i-1]][i-1];
	for(int i=0; ideep[y]) swap(x,y);//y更深
	for(int i=22; i>=0; i--) {
		//用倍增查到相同深度的两个(祖先)节点
		if(deep[x]<=deep[f[y][i]])
			y=f[y][i];
	}
	if(x==y) return x;
	for(int i=22; i>=0; i--) {
		//用同时倍增查到相同的祖先节点,其实就是一个数可以用二进制表示出来
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	}
	return f[x][0];
}
inline int readint() {
	//只能读取非负int
	char c=getchar();
	while(!isdigit(c)) c=getchar();
	int x=0;
	while(isdigit(c)) {
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
int buf[10];//声明成全局变量可以减少开销
inline void writeint(int i) {
	//只能输出非负int
	int p=0;
	if(i==0) p++;//特殊情况:i等于0的时候需要输出0,而不是什么也不输出
	else while(i) {
			buf[p++]=i%10;
			i/=10;
		}
	for(int j=p-1; j>=0; j--) putchar('0'+buf[j]); //逆序输出
}
int main() {
	int T;
	T=readint();
	while(T--) {
		n=readint(),m=readint();
		for(int i=1; i<=n; ++i) a[i].clear();
		for(int i=1; i<=m; ++i) v[i].clear();
		int x,y,w;
		for(int i=1; i
未经允许不得转载!hdu6115 Factory(lca)

update

纸上得来终觉浅, 绝知此事须躬行。