题目大意：给出N个点，M条边和一个人的起始位置，然后给出一系列操作
操作A: 0 u 询问这个人走到u这个位置需要几分钟
操作B: 1 i w，将第i条边的权值改成w
解题思路：第一个操作比较简单，第二个操作的话也不难。
在dfs纪录结点出现的顺序的时候，顺便记录一下每个点的pre，为第二个操作做准备。
执行第二个操作时，先把本来的边改变一下，再用一次dfs将该边以下的边全部该变一下就好了，，这时pre数组就有用了，因为它标记了哪几个点是和该边有关的
#include <cstdio>
#include <cstring>
#define N 100010
#define M 200010
struct Edge{
int from, to,
next, dis;
}E[M];
int head[N], first[N], dis[N], pre[N], ver[M], depth[M], dp[M][
63];
int tot, n, cnt,
pos,
m;
bool vis[N];
void AddEdge(
int u,
int v,
int c) {
E[tot].from = u; E[tot].to = v; E[tot].
next = head[u]; E[tot].dis = c; head[u] = tot++;
u = u ^ v; v = u ^ v; u = u ^ v;
E[tot].from = u; E[tot].to = v; E[tot].
next = head[u]; E[tot].dis = c; head[u] = tot++;
}
void init() {
memset(head, -
1, sizeof(head));
tot =
0;
int u, v, c;
for (
int i =
0; i < n -
1; i++) {
scanf(
"%d%d%d", &u, &v, &c);
AddEdge(u, v, c);
}
}
void RMQ() {
for (
int i =
1; i <= tot; i++)
dp[i][
0] = i;
int a, b;
for (
int j =
1; (
1 << j) <= tot; j++)
for (
int i =
1; i + (
1 << j) -
1 <= tot; i++) {
a = dp[i][j-
1];
b = dp[i + (
1 << (j -
1))][j-
1];
if (depth[a] < depth[b])
dp[i][j] = a;
else
dp[i][j] = b;
}
}
void dfs(
int u,
int dep) {
vis[u] = true; ver[++tot] = u; first[u] = tot; depth[tot] = dep;
for (
int i = head[u]; ~i; i = E[i].
next) {
int v = E[i].to;
if (!vis[v]) {
dis[v] = dis[u] + E[i].dis;
pre[v] = u;
dfs(v, dep +
1);
ver[++tot] = u; depth[tot] = dep;
}
}
}
char question[
100];
void change(
int u) {
for (
int i = head[u]; ~i; i = E[i].
next) {
int v = E[i].to;
if (pre[v] == u) {
dis[v] = dis[u] + E[i].dis;
change(v);
}
}
}
int Query(
int x,
int y) {
int k =
0;
while (
1 << (k +
1) <= (
y -
x +
1)) k++;
int a = dp[
x][k];
int b = dp[
y - (
1 << k) +
1][k];
if (depth[a] < depth[b])
return a;
return b;
}
int LCA(
int u,
int v) {
u = first[u];
v = first[v];
if (u > v) {
u = u ^ v; v = u ^ v; u = u ^ v;
}
int c = Query(u, v);
return ver[c];
}
void solve() {
memset(vis,
0, sizeof(vis));
dis[
1] =
0; tot =
0; pre[
1] =
1;
dfs(
1,
1);
RMQ();
int op, u, v;
while (
m--) {
scanf(
"%d", &op);
if (op ==
0) {
scanf(
"%d", &v);
int lca = LCA(
pos, v);
printf(
"%d\n", dis[
pos] + dis[v] -
2 * dis[lca]);
pos = v;
}
else {
scanf(
"%d%d", &u, &v);
u--;
E[u
*2].dis = E[(u *
2)^
1].dis = v;
int from = E[u
*2].from;
int to = E[u
*2].to;
if (pre[from] == to) {
dis[from] = dis[to] + E[u *
2].dis;
change(from);
}
else {
dis[to] = dis[from] + E[u *
2].dis;
change(to);
}
}
}
}
int main() {
while (scanf(
"%d%d%d", &n, &
m, &
pos) != EOF) {
init();
solve();
}
return 0;
}
