|
链接：https://vjudge.net/problem/HDU-2586
题意：
勇气小镇是一个有着n个房屋的小镇，为什么把它叫做勇气小镇呢，这个故事就要从勇气小镇成立的那天说起了，修建小镇的时候，为了让小镇有特色，镇长特地只修了n-1条路，并且规定说，所有在勇气小镇的村民，每一次出门必须规划好路线, 路线必须满足在到达终点之前绝对不走回头路。每个人都要这样，不然那个人就不配在小镇生活下去，因为他没有这个勇气。事实上，这并不能算一项挑战，因为n-1条路已经连通了每户人家，不回头地从起点到终点，只是一个时间上的问题。由于小镇上的福利特别好，所以小懒入住了这个小镇，他规划了m次的行程，每次从L房屋到R房屋,他想问你他每次从L房屋到R房屋需要走多远的路。
思路：
Tarjan离线算法， 第i个查询的最短路为dis[s[i]]+dis[e[i]]-2*dis[fas[i]] SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
代码：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int MAXN = 4e4+10;
struct Node
{
int from_, to_, dist_;
Node(int from, int to, int dist):from_(from), to_(to), dist_(dist){}
};
vector G[MAXN];
int fa[MAXN], dis[MAXN];
int vis[MAXN], fas[MAXN];
int s[MAXN], e[MAXN];
int n, m, l, r, v;
int root, res;
int Get_F(int x)
{
if (fa[x] == x)
return x;
fa[x] = Get_F(fa[x]);
return fa[x];
}
void Merge(int u, int v)
{
int tv = Get_F(v);
int tu = Get_F(u);
if (tv != tu)
fa[v] = u;
}
void Tarjan(int u)
{
vis[u] = 1;
for (int i = 1;i t;
while (t--)
{
cin >> n >> m;
init();
for (int i = 1;i < n;i++)
{
cin >> l >> r >> v;
G[l].emplace_back(l, r, v);
G[r].emplace_back(r, l, v);
}
for (int i = 1;i > l >> r;
s[i] = l;
e[i] = r;
}
dis[1] = 0;
Tarjan(1);
for (int i = 1;i |