树链剖分模板题。边权转点权的操作十分经典，用两个点中深度较大的存储边权（因为父亲唯一），然后就转化为点权的操作了。轻度卡常即可通过，比如线段树查询时写非递归版等。
时间复杂度 \(O(n \log n + q \log^2 n )\)。
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#define N 2000010using namespace std;vector<int> G[N];
int dep[N],top[N],fa[N],siz[N],son[N],id[N],rev[N],ans1[N],ans2[N],eid[N],tot;
struct E
{int u,v;
}e[N];int n,q;struct T
{int t[N * 4];void update( int u , int l , int r , int L , int R , int x ){if( L > R ) return;if( L <= l && r <= R ){t[u] = x;return;}if( t[u] ){t[u << 1] = t[u];t[u << 1 | 1] = t[u];t[u] = 0;}int mid = ( l + r ) >> 1;if( L <= mid ) update( u << 1 , l , mid , L , R , x );if( R > mid ) update( u << 1 | 1 , mid + 1 , r , L , R , x );return;}int que( int p ){int l = 1,r = n,u = 1,mid;while( l < r ){mid = ( l + r ) >> 1;if( t[u] ){t[u << 1] = t[u];t[u << 1 | 1] = t[u];t[u] = 0;}if( p <= mid ) r = mid,u = u << 1;else l = mid + 1,u = u << 1 | 1;}return t[u];}
}tr;void upd( int u , int v , int x )
{while( top[u] != top[v] ){ if( dep[top[u]] > dep[top[v]] ) swap( u , v );tr.update( 1 , 1 , n , id[top[v]] , id[v] , x );v = fa[top[v]];}if( dep[u] > dep[v] ) swap( u , v );tr.update( 1 , 1 , n , id[u] + 1 , id[v] , x );//由于是边权，故 LCA 不属于修改范围return;
}void dfs1( int u , int f )
{fa[u] = f;dep[u] = dep[f] + 1;siz[u] = 1;for( auto v : G[u] ){if( v == f ) continue;dfs1( v , u );siz[u] += siz[v];if( siz[v] > siz[son[u]] )son[u] = v;}return;
}void dfs2( int u , int f , int flag )
{id[u] = ++ tot;rev[tot] = u;if( flag ) top[u] = u;else top[u] = top[f];if( son[u] )dfs2( son[u] , u , 0 );for( auto v : G[u] ){if( v == f || v == son[u] ) continue;dfs2( v , u , 1 );}return;
}int read( void )
{int x = 0;char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ) x = x * 10 + ch - '0',ch = getchar();return x;
}void write( int x )
{if( x <= 9 ){putchar( x + '0' );return;}write( x / 10 );putchar( x % 10 + '0' );return;
}int main()
{int u,v;cin >> n >> q;for( int i = 1 ; i < n ; i ++ ){u = read(),v = read();e[i].u = u,e[i].v = v;G[u].push_back( v );G[v].push_back( u );}dfs1( 1 , 0 );dfs2( 1 , 0 , 1 );for( int i = 1 ; i <= q ; i ++ ){u = read(),v = read();upd( u , v , i );}for( int i = 1 ; i <= n ; i ++ )ans1[i] = tr.que( id[i] );for( int i = 1 ; i < n ; i ++ ){if( dep[e[i].u] < dep[e[i].v] ) swap( e[i].u , e[i].v );write( ans1[e[i].u] ),putchar( ' ' );}return 0;
}