题意：
给定一棵含n个结点的树和树的边权，共有q次操作，分为两种
0 c ：求从位置s到c的距离，然后s变成c
1 a b:把第a条边的权值变为b
边权处理一般有两种方案：
1.化边为点
即将所有的n-1条边上都增加一个节点，点权即边权，再有2n-1个节点的新树上进行点权的树链剖分即可
（一般不用
2.边附点
将边权附加在它深度更深的端点上（dep[v] > dep[u] ）,处理x，y之间的路径时其他操作和之前一样，只是最后不处理x，y的lca的点权（因为它点权所代表的的边权不在这条路径上）：
最后一步是：ans += query( 1 ,dfn[son[x]] ,dfn[y] ); 或 ans += query( 1 ,dfn[x]+1 ,dfn[y] );
注意当x==y时x，y本沈就是lca，直接不进行操作return就行
这个题写了1天也没过orz
先是wa： 问题就是上面说到的x==y时的处理没有注意
然后就一直tle，问题不明 ，线段树改成了结构体写法还是tle
贴一下代码，以后可能会发现错误在哪：
//树链剖分 b #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define fi first #define se second #define rep( i ,x ,y ) for( int i= x; i<= y ;i++ ) #define reb( i ,y ,x ) for( int i= y; i>= x ;i-- ) #define mem( a ,x ) memset( a ,x ,sizeof(a)) #define lson pos<<1 ,l ,m #define rson pos<<1|1 ,m+1 ,r using namespace std; typedef long long ll; typedef long double ld; typedef pair<int ,int> pii; typedef pair<ll ,ll> pll; typedef pair<string ,int> psi; const int inf = 0x3f3f3f3f; const int N = 100005; const int M = 1000005; struct Edge{ int to ,val ,next; }edge[N<<1]; struct E{ int u ,v ,c; }e[N<<1]; struct Tree{ int left ,right; int t ,lazy; }tree[N<<2]; int val[N] ,tr[N<<2]; int head[N]; int dep[N] ,dfn[N] ,son[N] ,fa[N]; int rnk[N] ,sz[N] ,top[N]; int cnt = 0,tot = 0 ,n ,q ,s ; void init( ){ cnt = tot =0; dep[1] = val[1] = 0; mem( head ,0 ); mem( son , 0 ); } void add_edge( int u ,int v ){ edge[++cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt; } // sgement tree void push_up( int pos ){ tree[pos].t = tree[pos<<1].t + tree[pos<<1|1].t; } void build( int pos , int l ,int r ){ tree[pos].left = l; tree[pos].right= r; if( l==r ){ tree[pos].t = val[ rnk[l] ]; return; } int m = (l+r)>>1; build( lson ); build( rson ); push_up( pos ); } void updata( int pos ,int p ,int v ){ //cout<<tree[pos].left<<" "<<tree[pos].right<<endl; if( tree[pos].left == p && tree[pos].right ==p ){ tree[pos].t = v; return; } int m = (tree[pos].left+tree[pos].right)>>1; if( p<=m)updata( pos<<1 ,p ,v ); else updata( pos<<1|1 ,p ,v ); push_up( pos ); } int query( int pos ,int l ,int r ){ if( l <= tree[pos].left && tree[pos].right <= r){ return tree[pos].t; } int ans = 0; int m = ( tree[pos].left+tree[pos].right )>>1; if( m >= l )ans += query( pos<<1 ,l ,r ); if( m < r ) ans += query( pos<<1|1 ,l ,r ); return ans; } // tree - chain // dfs 1-- dep ,sz ,fa ,son void dfs1( int u ,int f ){ sz[u] = 1; for( int i = head[u]; i ;i = edge[i].next ){ int v = edge[i].to; if( v == f )continue; dep[v] = dep[u] + 1; fa[v] = u; dfs1( v ,u ); sz[u] += sz[v]; if( sz[v] >sz[ son[u] ] )son[u] = v; } } void dfs2( int u ,int t ){ dfn[u] = ++tot; top[u] = t; rnk[tot] = u; if( son[u] )dfs2( son[u] ,t ); for( int i = head[u] ;i ;i = edge[i].next ){ int v = edge[i].to; if( v!= fa[u] && v!= son[u] )dfs2(v,v); } } int LCA( int x ,int y ){ int fx = top[x] ,fy = top[y]; while( fx != fy ){ if( dep[x] < dep[y] )swap(x ,y) ,swap( fx ,fy ); x= fa[fx] ,fx = top[x]; } return dep[x] < dep[y] ? x : y ; } /*void c_updata( int x ,int y ,int v ){ int fx = top[x] ,fy = top[y]; while( fx != fy ){ if( dep[fx] < dep[fy] )swap(x ,y) ,swap(fx ,fy); updata( 1 ,1 ,n ,dfn[fx] ,dfn[x] ,v); x = f[x] ,fx = top[x]; } if( dfn[x] > dfn[y] )swap( x ,y ); updata( 1 ,1 ,n ,dfn[x] ,dfn[y] ,v); } */ int c_query( int x ,int y ){ int fx = top[x] ,fy = top[y]; int ans = 0; while( fx != fy ){ if( dep[fx] < dep[fy] )swap(x ,y) ,swap(fx ,fy); ans += query( 1 ,dfn[fx] ,dfn[x] ); x = fa[x] ,fx = top[x]; } if( x==y )return ans; if( dfn[x] > dfn[y] )swap( x ,y ); //cout<<x<<" son2 "<<son[x]<<endl; // x = son[x]; 致死错误 if(dfn[x] != dfn[y])ans += query( 1 ,dfn[son[x]] ,dfn[y] ); return ans ; } void rev_edge( ){ rep( i ,1 ,n-1 ){ if( dep[e[i].v] > dep[e[i].u] )val[e[i].v] = e[i].c; else val[e[i].u] = e[i].c; //cout<<" rev_edge "<<e[i].u<<" "<<val[e[i].u]<<" "<<e[i].v<<" "<<val[e[i].v]<<endl; } } int main( ){ scanf( "%d%d%d" ,&n ,&q ,&s ) ; //init(); rep( i ,1 ,n-1 ){ scanf("%d%d%d" ,&e[i].v ,&e[i].u ,&e[i].c); add_edge( e[i].u ,e[i].v); add_edge( e[i].v ,e[i].u); } dfs1( 1 ,1 ); dfs2( 1 ,1 ); rev_edge( ); build( 1 ,1 ,n ); int op ,l ,r ,z; while( q-- ){ scanf("%d" ,&op ); if( op ){ scanf("%d%d",&l ,&z); if( dep[e[l].v] > dep[e[l].u] )l = e[l].v; else l = e[l].u; updata( 1 ,dfn[l] ,z ); } else{ scanf("%d" ,&l ); printf( "%d " ,c_query( s ,l) ); s = l; } } return 0; }
别人可以过的代码：https://www.cnblogs.com/yaoyueduzhen/p/5311230.html
我觉得就边权附到节点那个过程我们有些许差异，其他地方基本一样啊，为什么我写的过不了呢？
sad，陷入了迷惑与巨大的沮丧中
找到错误了！
在函数c_query里：
int c_query( int x ,int y ){ int fx = top[x] ,fy = top[y]; int ans = 0; while( fx != fy ){ if( dep[fx] < dep[fy] )swap(x ,y) ,swap(fx ,fy); ans += query( 1 ,dfn[fx] ,dfn[x] ); x = fa[x] ,fx = top[x]; } if( x==y )return ans; if( dfn[x] > dfn[y] )swap( x ,y ); //cout<<x<<" son2 "<<son[x]<<endl; // x = son[x]; 致死错误 if(dfn[x] != dfn[y])ans += query( 1 ,dfn[son[x]] ,dfn[y] ); return ans ; }
这一句：
x = fa[x] ,fx = top[x];
应为：
x = fa[fx] ,fx = top[x];
这里前面思路是对的，就是手残，下意识，肌肉记忆
事实上，代码我后来又重写了两遍 ，这里依然是写错的，人的大脑真的很神奇
改过来后就过了