题目 把边权看作点权
不知道为啥N=1e5+5会wa,数组要开大点
#include<iostream> #include<string.h> #include<stdio.h> using namespace std; const int N=2e5+5; int fa[N],son[N],dep[N],top[N],siz[N],pos[N],fp[N]; struct Edge{ int to,next; Edge(){} Edge(int to,int next):to(to),next(next){} }E[N]; int head[N],tot; inline void addedge(int u,int v){ E[tot]=Edge(v,head[u]); head[u]=tot++; } void dfs(int x,int f,int d){ siz[x]=1,fa[x]=f,dep[x]=d; for(int i=head[x];~i;i=E[i].next)if(E[i].to!=f){ int v=E[i].to; dfs(v,x,d+1); siz[x]+=siz[v]; if(son[v]==-1||siz[v]>siz[son[x]])son[x]=v; } } int cnt; void dfs2(int x,int nowtop){ pos[x]=++cnt,top[x]=nowtop,fp[pos[x]]=x; if(son[x]==-1)return; dfs2(son[x],nowtop); for(int i=head[x];~i;i=E[i].next){ int v=E[i].to; if(v!=fa[x]&&v!=son[x])dfs2(v,v); } } struct Node{ int l,r,sum; }T[N<<2]; void build(int i,int l,int r){ T[i]=(Node){l,r,0}; if(l==r)return; int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); } void pushup(int i){T[i].sum=T[i<<1].sum+T[i<<1|1].sum;} void update(int i,int x,int val){ if(T[i].l==x&&T[i].r==x){ T[i].sum=val;return; } int mid=(T[i].l+T[i].r)>>1; if(x<=mid)update(i<<1,x,val); else update(i<<1|1,x,val); pushup(i); } int query(int i,int l,int r){ if(T[i].l==l&&T[i].r==r)return T[i].sum; int mid=(T[i].l+T[i].r)>>1; if(r<=mid)return query(i<<1,l,r); if(l>mid)return query(i<<1|1,l,r); return query(i<<1,l,mid)+query(i<<1|1,mid+1,r); } void init(){ tot=0,memset(head,-1,sizeof(head)); cnt=0,memset(son,-1,sizeof(son)); } int Q(int u,int v){ int f1=top[u],f2=top[v],ans=0; while(f1^f2){ if(dep[f1]<dep[f2])swap(f1,f2),swap(u,v); ans+=query(1,pos[f1],pos[u]); u=fa[f1],f1=top[u]; } if(u==v)return ans; if(dep[u]>dep[v])swap(u,v); return ans+query(1,pos[son[u]],pos[v]); } int e[N][3],u,v,now,n,q,op; int main(){ init(); scanf("%d%d%d",&n,&q,&now); for(int i=1;i<n;++i){ scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]); addedge(e[i][0],e[i][1]),addedge(e[i][1],e[i][0]); } dfs(1,0,0); dfs2(1,1); build(1,0,cnt); for(int i=1;i<n;++i){ if(dep[e[i][0]]>dep[e[i][1]])swap(e[i][0],e[i][1]); update(1,pos[e[i][1]],e[i][2]); } while(q--){ scanf("%d%d",&op,&u); if(op)scanf("%d",&v),update(1,pos[e[u][1]],v); else printf("%d\n",Q(u,now)),now=u; } return 0; }