#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <stack>
using namespace std;

#define MAX_N 100005
#define MAX_M 200005

struct node
{
       int t, next, len;
       node (int _t = 0, int _next = -1, int _len = 0)
       {
            t = _t, next = _next, len = _len;
       }
};
 
node tree[MAX_M];
int tf[MAX_N], st[MAX_N], en[MAX_N];

int ord[MAX_M], first[MAX_N], dep[MAX_M], dist[MAX_N];
int f[MAX_M][19], logn[MAX_M];// logn[i]: log (2, i)
int fa[MAX_N], x[MAX_N], y[MAX_N], len[MAX_N];
int num, nft, tot;

inline void add(int a, int b, int c)
{
       tot++;
       tree[tot] = node (b, tf[a], c);
       tf[a] = tot;
}

void dfs(int v, int deep)
{
     ord[++num] = v, dep[num] = deep, first[v] = num;
     st[v] = ++nft;
     for (int i = tf[v]; i != -1; i = tree[i].next)
     {
         if (!first[tree[i].t])
         {
            dist[tree[i].t] = dist[v] + tree[i].len;
            fa[tree[i].t] = v;
            dfs (tree[i].t, deep + 1);
            ord[++num] = v, dep[num] = deep;   
         }
     }
     en[v] = nft;
}

void RMQ_LCA(void)
{
     logn[0] = -1;
     for (int i = 1; i <= num; i++)
         f[i][0] = i;
     for (int j = 1, s = 1; s <= num; s <<= 1, j++)
     {
         for (int i = 1; i + s<= num; i++)
         {
             if (dep[f[i][j - 1]] < dep[f[i + s][j - 1]])
                f[i][j] = f[i][j - 1];
             else f[i][j] = f[i + s][j - 1];
         }
     }
}

int LCA(int a, int b)
{
    a = first[a], b = first[b];
    if (a > b) swap (a, b);
    int k = logn[b - a + 1], s = 1 << k;
    if (dep[f[a][k]] < dep[f[b - s + 1][k]])
       return ord[f[a][k]];
    else return ord[f[b - s + 1][k]];
}

int sum[MAX_N * 3];
int n, m, q, now;
int sl, sr, dt;

inline void down(int root)
{
       sum[root * 2] += sum[root],
       sum[root * 2 + 1] += sum[root],
       sum[root] = 0;
}

void insert (int l, int r, int idx)
{
     if (sr < l || sl > r) return ;
     if (sl <= l && r <= sr)
     {
        sum[idx] += dt;
        return ;
     }
     down (idx);
     int mid = (l + r) >> 1;
     if (sr <= l) insert (l, mid, idx << 1);
     else 
     {
          insert (l, mid, idx << 1);
          insert (mid + 1, r, (idx << 1) + 1);
     }
}

int query (int l, int r, int idx)
{
    if (l == r) return sum[idx];
    down (idx);
    int mid = (l + r) >> 1;
    if (sl <= mid) return  query (l, mid, idx << 1) ;
    else return query (mid + 1, r, (idx << 1) + 1);
}

int main(void)
{
    scanf("%d%d%d", &n, &m, &now);
    logn[0] = -1;
    for (int i = 1; i < MAX_M; i++)
        logn[i] = (i & (i - 1)) ? logn[i - 1]: logn[i - 1] + 1;
    memset (tf, -1, sizeof (tf));
    for (int i = 1; i < n; i++)
    {   
        scanf ("%d%d%d", x + i, y + i, len + i);
        add (x[i], y[i], len[i]);
        add (y[i], x[i], len[i]);
	}
	dfs (1 ,0);
	RMQ_LCA();
	for (int i = 1, sign, t, w; i <= m; i++)
	{
        scanf ("%d", &sign);
        if (sign == 1)
        {
           scanf ("%d%d", &t, &w);
           dt = w - len[t], len[t] = w;
           if (fa[x[t]] == y[t]) t = x[t];
           else t = y[t];
           sl = st[t], sr = en[t];
           insert (1, n, 1);
        }
        else
        {
            scanf ("%d", &t);
            int lca = LCA (now, t), p;
            sl = st[now], p = dist[now] + query (1, n, 1);
            sl = st[t], p += dist[t] + query (1, n, 1);
            sl = st[lca], p -= 2 * (dist[lca] + query (1, n, 1));
            printf ("%d\n", p);
            now = t;
        }
    }
	return 0;
}

• Re:LCA ----> RMQ (119) lz1 2011-07-31 19:57:17