1103: [POI2007]大都市meg
题目：传送门
简要题意：
给你一棵树，给出每条边的权值，两个操作：1、询问根到编号x的最短路径的权值和 2、修改一条边的边权
题解：
很明显啊，看懂了题基本上就A了
一个树剖的板子啊...(其实不是最优解...卡时间过的嘿嘿)
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
struct node
{
int x,y,next;
}a[];int len,last[];
void ins(int x,int y)
{
len++;a[len].x=x;a[len].y=y;
a[len].next=last[x];last[x]=len;
}
struct trnode
{
int l,r,lc,rc,c;
}tr[];int trlen;
void bt(int l,int r)
{
int now=++trlen;
tr[now].l=l;tr[now].r=r;tr[now].c=;
tr[now].lc=tr[now].rc=-;
if(l<r)
{
int mid=(l+r)/;
tr[now].lc=trlen+;bt(l,mid);
tr[now].rc=trlen+;bt(mid+,r);
}
}
int fa[],dep[],son[],tot[];
void pre_tree_node(int x)
{
tot[x]=;son[x]=;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa[x])
{
fa[y]=x;
dep[y]=dep[x]+;
pre_tree_node(y);
if(tot[y]>tot[son[x]])son[x]=y;
tot[x]+=tot[y];
}
}
}
int z,ys[],top[];
void pre_tree_edge(int x,int tp)
{
ys[x]=++z;top[x]=tp;
if(son[x]!=)pre_tree_edge(son[x],tp);
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa[x] && y!=son[x])
pre_tree_edge(y,y);
}
}
void change(int now,int p,int c)
{
if(tr[now].l==tr[now].r){tr[now].c=c;return ;}
int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/;
if(p<=mid)change(lc,p,c);
else change(rc,p,c);
tr[now].c=tr[lc].c+tr[rc].c;
}
int getsum(int now,int l,int r)
{
if(tr[now].l==l && tr[now].r==r)return tr[now].c;
int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/;
if(r<=mid) return getsum(lc,l,r);
else if(l>mid) return getsum(rc,l,r);
else return getsum(lc,l,mid)+getsum(rc,mid+,r);
}
int solve(int x,int y)
{
int tx=top[x],ty=top[y],ans=;
while(tx!=ty)
{
if(dep[tx]>dep[ty])
{
swap(x,y);
swap(tx,ty);
}
ans+=getsum(,ys[ty],ys[y]);
y=fa[ty];ty=top[y];
}
if(x==y)return ans;
else
{
if(dep[x]>dep[y])swap(x,y);
return ans+getsum(,ys[son[x]],ys[y]);
}
}
struct edge
{
int x,y;
}e[];
int n;char st[];
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d%d",&e[i].x,&e[i].y);
ins(e[i].x,e[i].y);
ins(e[i].y,e[i].x);
}
dep[]=;fa[]=;pre_tree_node();
z=;pre_tree_edge(,);
trlen=;bt(,z);
int m;scanf("%d",&m);
for(int i=;i<n;i++)
{
if(dep[e[i].x]>dep[e[i].y])swap(e[i].x,e[i].y);
change(,ys[e[i].y],);
}
for(int i=;i<=n+m-;i++)
{
scanf("%s",st+);
if(st[]=='A')
{
int x,y;
scanf("%d%d",&x,&y);
if(dep[x]>dep[y])swap(x,y);
change(,ys[y],);
}
else
{
int x;
scanf("%d",&x);
printf("%d\n",solve(,x));
}
}
return ;
}