程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2586 How Far Away？（Tarjan離線算法求lca）

HDU 2586 How Far Away？（Tarjan離線算法求lca）

編輯：C++入門知識

HDU 2586 How Far Away？（Tarjan離線算法求lca）

題意：給定一棵樹n個節點m個詢問，每次詢問兩個節點之間的距離。

思路：Tarjan離線算法求lca。

這題一開始交了n發一直爆棧.......百度了一下大概說的是這樣hdu用的是windows服務器所以棧大小極其坑爹,稍微深一點的遞歸就會爆棧（正式比賽一般不會爆）

解決方法就是加一句#pragma comment(linker, /STACK:1024000000,1024000000) 用c++交就好.....當然這只是針對比較坑爹oj來說的取巧的方法

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#define eps 1e-6 
#define LL long long  
using namespace std;  
#pragma comment(linker, /STACK:1024000000,1024000000) 
const int maxn = 50000;
//const int INF = 0x3f3f3f3f;
int dist[maxn], pnt[maxn], ans[maxn];
bool vis[maxn];
vector G[maxn], w[maxn], query[maxn], num[maxn];
int n, m;
int find(int x) {
	if(x == pnt[x]) return x;
	return pnt[x] = find(pnt[x]);
}
void dfs(int u, int val) {
	dist[u] = val; vis[u] = 1; pnt[u] = u;
	int sz1 = G[u].size();
	for(int i = 0; i < sz1; i++) {
		int v = G[u][i];
		if(vis[v]) continue;
		dfs(v, val+w[u][i]);
		pnt[v] = u;
	}
	int sz2 = query[u].size();
	for(int i = 0; i < sz2; i++) {
		int v = query[u][i];
		if(vis[v]) ans[num[u][i]] = dist[u] + dist[v] - 2*dist[find(v)];
	}
} 
void init() {
	memset(vis, 0, sizeof(vis));
	for(int i = 1; i <= n; i++) {
		G[i].clear(); 
		w[i].clear(); 
		query[i].clear(); 
		num[i].clear();
	}
}
int main() {
//	freopen(input.txt, r, stdin);
	int T; cin >> T;
	while(T--) {
		cin >> n >> m;
		init();
		for(int i = 0; i < n-1; i++) {
			int u, v, d;
			scanf(%d%d%d, &u, &v, &d);
			G[u].push_back(v);
			G[v].push_back(u);
			w[u].push_back(d);
			w[v].push_back(d);
		}
		for(int i = 0; i < m; i++) {
			int u, v;
			scanf(%d%d, &u, &v);
			query[u].push_back(v);
			query[v].push_back(u);
			num[u].push_back(i);
			num[v].push_back(i);
		}
		dfs(1, 0);
		for(int i = 0; i < m; i++) printf(%d
, ans[i]);
	}
	return 0;
}