本文共 3561 字，大约阅读时间需要 11 分钟。

一、题意

一棵n个点的带边权的树，q次询问，每次询问一个区间[l,r]，求max(dist(u,v)),l≤u≤v≤r。

n,q都是3e5，边权是1e9。

二、题解

直径指的是带权直径。

需要发现一个性质，就是两个连续区间合并的时候，合并后的区间的直径的端点是合并前的四个端点中的两个。

通过枚举确定是哪两个。

st[i][j]表示[i,i+(1<<j)-1]的直径的端点。

预处理出st就可以在线回答询问了。

三、感受

不能随心所欲地乱写，要卡常。

（1）欧拉序求lca

（2）log2函数预处理

四、代码

#include
   
    #define pb push_back#define fi first#define se second#define sz(x)  (int)x.size()#define cl(x)  x.clear()#define all(x)  x.begin() , x.end()#define rep(i , x , n)  for(int i = x ; i <= n ; i ++)#define per(i , n , x)  for(int i = n ; i >= x ; i --)#define mem0(x)  memset(x , 0 , sizeof(x))#define mem_1(x)  memset(x , -1 , sizeof(x))#define mem_inf(x)  memset(x , 0x3f , sizeof(x))#define debug(x)  cerr << #x << " = " << x << '\n'#define ddebug(x , y)  cerr << #x << " = " << x << "   " << #y << " = " << y << '\n'#define ios std::ios::sync_with_stdio(false) , cin.tie(0)using namespace std ;typedef long long ll ;typedef long double ld ;typedef pair
    
      pii ;typedef pair
     
       pll ;const int mod = 998244353 ;const int maxn = 3e5 + 10 ;const int inf = 0x3f3f3f3f ;const double eps = 1e-6 ; mt19937  rnd(chrono::high_resolution_clock::now().time_since_epoch().count()) ; int n , q ;int dep[maxn] ;ll d[maxn] ;pii st[maxn][25] ;vector
      
        g[maxn] ;void dfs1(int f , int u , int deep , ll dd){   dep[u] = deep ;   d[u] = dd ;   for(auto x : g[u])   {     int v = x.fi ;     int w = x.se ;     if(v == f)  continue ;     dfs1(u , v , deep + 1 , dd + w) ;   }}int cnt = 0 ;int a[maxn << 1] , pos[maxn] ;int f[maxn << 1][25] ;void dfs2(int fa , int u){    a[++ cnt] = u ;    pos[u] = cnt ;    for(auto x : g[u])    {        int v = x.fi ;        if(v == fa)  continue ;        dfs2(u , v) ;        a[++ cnt] = u ;    }}int lg[maxn << 1] ;void init1(){    lg[1] = 0;  for (int i = 2; i <= cnt; i++) lg[i] = lg[i >> 1] + 1;    rep(i , 1 , cnt)  f[i][0] = a[i] ;    rep(j , 1 , 20)  rep(i , 1 , cnt - (1 << j))          if(dep[f[i][j - 1]] < dep[f[i + (1 << (j - 1))][j - 1]])  f[i][j] = f[i][j - 1] ;      else  f[i][j] = f[i + (1 << (j - 1))][j - 1] ;}int lca(int x , int y){    int ans ;    if(pos[x] > pos[y])  swap(x , y) ;    int l1 = pos[x] , l2 = pos[y] ;    //int len = log2(l2 - l1 + 1) ;    int len = lg[l2 - l1 + 1] ;    if(dep[f[l1][len]] < dep[f[l2 - (1 << len) + 1][len]])  ans = f[l1][len] ;    else  ans = f[l2 - (1 << len) + 1][len] ;    return ans ;}ll dis(int u , int v){    return d[u] + d[v] - 2ll * d[lca(u , v)] ;}pii t[15] ;pii merge(pii x , pii y){    int temp = 0 ;    t[0] = {x.fi , x.se} ;    t[1] = {y.fi , y.se} ;    t[2] = {x.fi , y.fi} ;    t[3] = {x.fi , y.se} ;    t[4] = {x.se , y.fi} ;    t[5] = {x.se , y.se} ;    rep(i , 1 , 5)  if(dis(t[i].fi , t[i].se) > dis(t[temp].fi , t[temp].se))  temp = i ;    return t[temp] ;}void init(){   for(int i = 1 ; i <= n ; i ++)  st[i][0] = {i , i} ;    for(int j = 1 ; j <= 20 ; j ++)   for(int i = 1 ; i + (1 << j) - 1 <= n ; i ++)   st[i][j] = merge(st[i][j - 1] , st[i + (1 << (j - 1))][j - 1]) ;}void prework(){    dfs1(1 , 1 , 0 , 0) ;    dfs2(1 , 1) ;        init1() ;    init() ;}pii query(int l , int r){    int len = lg[r - l + 1] ;   return merge(st[l][len] , st[r - (1 << len) + 1][len]) ; }ll solve(int l , int r){    pii ans = query(l , r) ;    return dis(ans.fi , ans.se) ;}int main(){    ios ;    cin >> n >> q ;    rep(i , 1 , n - 1)    {        int u , v , w ;        cin >> u >> v >> w ;        g[u].pb({v , w}) ;        g[v].pb({u , w}) ;    }    prework() ;    while(q --)    {        int l , r ;        cin >> l >> r ;        cout << solve(l , r) << '\n' ;    }    return 0 ;}