比赛 |
ZLXOI2015Day2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
ZLX的陨落 |
最终得分 |
100 |
用户昵称 |
ppfish |
运行时间 |
0.562 s |
代码语言 |
C++ |
内存使用 |
12.14 MiB |
提交时间 |
2015-10-30 20:20:50 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
template<class T>inline void Read(T &x)
{
int f = 1;
char t = getchar();
while (t < '0' || t > '9') {
if (t == '-') f = -1;
t = getchar();
}
x = 0;
while (t >= '0' && t <= '9') {
x = x * 10 + t - '0';
t = getchar();
}
x *= f;
}
int outp[105], tp;
template<class T>inline void write(T x)
{
if (x < 0) putchar('-'), x = -x;
tp = 0;
do {
outp[++tp] = x % 10;
x /= 10;
} while (x);
while (tp) putchar('0' + outp[tp]), tp --;
putchar('\n');
}
const int maxn = 100005;
const int maxm = 200005;
const int logn = 18;
int n, m, q;
int fst[maxn], u[maxm], v[maxm], w[maxm], nxt[maxm], e_cn;
int f[maxn][logn + 1], dep[maxn];
long long dis[maxn];
inline void addedge(int x, int y, int z)
{
e_cn ++;
u[e_cn] = x, v[e_cn] = y, w[e_cn] = z;
nxt[e_cn] = fst[x], fst[x] = e_cn;
}
void input()
{
int x, y, z;
Read(n), Read(m);
for (register int i = 1; i < n; i++) {
Read(x), Read(y), Read(z);
addedge(x, y, z);
addedge(y, x, z);
}
Read(q);
memset(f, -1, sizeof(f));
}
void dfs(int cn, int pr)
{
f[cn][0] = pr;
for (register int i = fst[cn]; i; i = nxt[i]) {
if (v[i] != pr) {
dis[v[i]] = dis[cn] + w[i];
dep[v[i]] = dep[cn] + 1;
dfs(v[i], cn);
}
}
}
void prepare()
{
dfs(1, -1);
for (register int k = 1; (1 << k) <= n; k++) {
for (register int i = 1; i <= n; i++) {
if (f[i][k - 1] != -1) {
f[i][k] = f[f[i][k - 1]][k - 1];
}
}
}
}
int lca(int x, int y)
{
if (dep[x] < dep[y]) swap(x, y);
for (register int k = logn; k >= 0; k--) {
if (f[x][k] != -1 && dep[f[x][k]] >= dep[y]) {
x = f[x][k];
}
}
if (x == y) return x;
for (register int k = logn; k >= 0; k--) {
if (f[x][k] != -1 && f[y][k] != -1 && f[x][k] != f[y][k]) {
x = f[x][k];
y = f[y][k];
}
}
return f[x][0];
}
void solve()
{
int x, y;
while (q --) {
Read(x), Read(y);
write(dis[x] + dis[y] - 2 * dis[lca(x, y)]);
}
}
int main()
{
freopen("ThefallingofZLX.in", "r", stdin);
freopen("ThefallingofZLX.out", "w", stdout);
input();
prepare();
solve();
fclose(stdin);
fclose(stdout);
return 0;
}