#include <iostream>
#include <vector>
using namespace std;

const int maxn=4*100005;

struct node
{
    int id,w,num;  //id表示编号，w为权值，num表示第几条路
};

struct tree   //线段树
{
  int l,r;
  int add;  //改变值
  int min;  //保存最小值
};

vector <node> v[maxn];
int st[maxn],en[maxn];  //dfs时每个结点第一次访问时的序号，最后一次访问时的序号
int e[maxn],ww[maxn];  // e[]为每条边的末端点，ww[] 表示第i条边的权值
int d[maxn],f[maxn],num[maxn]; //d[]为每一结点到根的距离，f[]为第一次访问结点时的序号，num[]保存欧拉序列每一点到根的距离
bool visit[maxn];
tree g[maxn];
int n,q,s,tt;  //s为始点，会改变,   tt为欧拉序列的结点数


int min(int a,int b)
{
    if (a<b) return a;
    else return b;
}

int max(int a,int b)
{
	if (a>b) return a;
	else return b;
}

void dfs(int u)
{
    tt++; f[u]=tt; num[tt]=d[u]; st[u]=tt;
    visit[u]=true;
    for (int i=0;i<(int)v[u].size();i++)
    {
        if (visit[v[u][i].id]==false)
        {
            d[v[u][i].id]=d[u]+v[u][i].w;
            e[v[u][i].num]=v[u][i].id;
			ww[v[u][i].num]=v[u][i].w;
            dfs(v[u][i].id);
            tt++; num[tt]=d[u];
        }
    }
    en[u]=tt;
}

void build(int l,int r,int t)
{
    g[t].l=l; g[t].r=r; g[t].add=0; g[t].min=999999999;
    if (l==r)
    {
        g[t].min=num[l];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,2*t);
    build(mid+1,r,2*t+1);
    g[t].min=min(g[2*t].min,g[2*t+1].min);
}

int find(int l,int r,int t)
{
    if (g[t].l==l && g[t].r==r)
    {
        return g[t].min;
    }

    g[2*t].add+=g[t].add; g[2*t+1].add+=g[t].add;
    g[2*t].min+=g[t].add; g[2*t+1].min+=g[t].add;
    g[t].add=0;

    int mid=(g[t].l+g[t].r)/2;
    if (l>=mid+1)
        return find(l,r,2*t+1);
    else if (r<=mid)
        return find(l,r,2*t);
    else
    {
        return min(find(l,mid,2*t),find(mid+1,r,2*t+1));
    }
}

void insert(int l,int r,int t,int k)
{
    if (g[t].l==l && g[t].r==r)
    {
        g[t].add+=k;
        g[t].min+=k;
        return ;
    }

    g[2*t].add+=g[t].add; g[2*t+1].add+=g[t].add;
    g[2*t].min+=g[t].add; g[2*t+1].min+=g[t].add;
    g[t].add=0;

    int mid=(g[t].l+g[t].r)/2;
    if (l>=mid+1)
        insert(l,r,2*t+1,k);
    else if (r<=mid)
        insert(l,r,2*t,k);
    else
    {
        insert(l,mid,2*t,k);
        insert(mid+1,r,2*t+1,k);
    }
    g[t].min=min(g[2*t].min,g[2*t+1].min);

}

void init()
{
    for (int i=1;i<=n;i++)
    {
        v[i].clear();
    }
}

int main()
{
    int i,a,b,c,ee;
    while (scanf("%d%d%d",&n,&q,&s))
    {
        init();
        for (i=1;i<=n-1;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            node p;
            p.id=b; p.w=c; p.num=i;
            v[a].push_back(p);
            p.id=a; p.w=c; p.num=i;
            v[b].push_back(p);
        }
        memset(visit,false,sizeof(visit));
        tt=0; d[1]=0;
        dfs(1);
 /*       for (i=1;i<=n;i++) printf("%d ",d[i]);
        printf("\n");
        for (i=1;i<=2*n-1;i++) printf("%d ",num[i]);
        printf("\n");
        for (i=1;i<=n;i++) printf("%d ",f[i]);
        printf("\n");
        for (i=1;i<=n;i++) printf("%d ",en[i]);
        printf("\n");
*/
        build(1,tt,1);
        while(q--)
        {
            scanf("%d",&a);
            if (a==0)
            {
                scanf("%d",&ee);
                int ans=find(min(f[s],f[ee]),max(f[s],f[ee]),1); //返回公共祖先到根的距离
                printf("%d\n",find(f[s],f[s],1)+find(f[ee],f[ee],1)-2*ans);
                s=ee;
            }
            else
            {
                scanf("%d%d",&b,&c);
                //当一条边的权值改变时，改变欧拉序列的一段，对应以其为根的下边的点都改变了，区间为这一个点在欧拉序列第一次出现的位置到最后一次出现的位置
                insert(st[e[b]],en[e[b]],1,c-ww[b]); 
            }
        }
    }
    return 0;
}

• This Is What I Believe (0) undikeengique 2012-12-16 12:44:01
• Factors To Imagine About If You Want To Expand Food items In An Aquaponics Garden (0) undikeengique 2012-12-17 14:43:57
• Re:求救啊！！！！！无限RE啊！我的方法好清晰，用线段树来动态维护欧拉序列，我测试了好久感觉没错，可总是RE，求大牛指点！！ (13) Andreew 2021-08-18 17:59:16