挺进

zz:https://blog.csdn.net/rzo_kqp_orz/article/details/52280525
小Z又开始了ETG。ETG的地图是树形的，相邻两个房间有一定距离，一开始，系统会随机断掉一条边，这样，这张
地图就被分成了两个连通块。显然，狡猾的系统会把四个宝箱两两分布在每个联通的最远点对上。一开始，小Z会
出生在一个有宝箱的房间（系统还是有点良心的），然后小Z“咚咚咚咚”一路过关斩将走到有另外一个宝箱的所
在地（显然小Z走最短路），到达第二个宝箱所在地后，系统会又很良心地把他送到另一个连通块的某个宝箱处，
然后小Z又“咚咚咚咚咚”，拿到了最后一个宝箱。然后，他就通关了。显然对小Z来说通关是肯定的，所以小Z想
知道他最多会走多少距离。

Input
输入第一行包含一个整数N，表示房间个数。
接下来N-1行，每行3个正整数x,y,d表示，房间x与房间y的距离为d。
N<=100,000 ，di<=100,000 。

Output
输出一行，包含一个整数，表示小Z最远走的距离。

Sample Input
6
1 3 4
2 3 1
2 5 3
2 6 2
3 4 5

Sample Output
14

Data Constraint

对于50%的数据满足N<=1000 。
对于100%的数据满足

一句话题意
给出一棵树，你可以选择断掉某一条边，然后取生成的两棵树的直径和。求这个和的最大值。
【50%】n<=1000
枚举断哪一条边，然后暴力求直径。
【100%解法1】n<=10^5
用线段树维护树的直径。
枚举断哪一条边，这相当于分离出原树的一棵子树，我们可以在线段树中查找到这棵子树的直径，然后剩下的区间合并一下得到另一个直径。
如果用倍增求lca时间是O(n log^2)，会被卡。
如果用rmq求lca时间是O(n log)
//线段树维护树的直径：http://blog.csdn.net/rzo_kqp_orz/article/details/52280811
【100%解法2】
题解说这是裸的树形dp！？
题解原话：“裸的树形 DP，记录 d1[i] (最长链)，d2[i] (次长链)，fa[i] ( i 的父亲及以上的最长路)即可。时间复杂度O(n)。”
思路是非常简单的，但是维护过程打起来讨论较多。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std ;

#define N 100000 + 10
typedef long long ll ;
const int MAXN = 19 ;
struct Note
{
int a , b ;
ll len ;
Note ( int X = 0 , int Y = 0 , ll Z = 0 ) { a = X , b = Y , len = Z ; }
} T[4*N] , ret ;

int tab[2*N] ;
int RMQ[2*N][MAXN] ;
int Node[2*N] , Next[2*N] , Len[2*N] , Head[N] , tot = 1 ;
int S[2*N] , P[2*N] , Fir[N] , Dep[N] ;
int E[N] , D[N] , R[N] , DFN[N] ;
ll ans , Dist[N] ;
int n ;

void link( int u , int v , int w )
{
Node[++tot] = v ;
Next[tot] = Head[u] ;
Len[tot] = w ;
Head[u] = tot ;
}

void DFS( int x , int Fa )
{
D[++D[0]] = x ;//dfs序
S[++S[0]] = x ;
P[S[0]] = Dep[x] ;//进来的第i个点，深度为j
Fir[x] = S[0] ; //x点进来的时候
DFN[x] = D[0] ;
for (int p = Head[x] ; p ; p = Next[p] )
{
if ( Node[p] == Fa ) continue ;
Dep[Node[p]] = Dep[x] + 1 ;
Dist[Node[p]] = Dist[x] + Len[p] ;
DFS( Node[p] , x ) ;
S[++S[0]] = x ;
P[S[0]] = Dep[x] ;
R[x] = D[0] ;
}
}

void Pre()
{
for (int i = 1 ; i <= S[0] ; i ++ )
RMQ[i][0] = i , tab[i] = log(i) / log(2) ;
for (int j = 1 ; j < MAXN ; j ++ ) {
for (int i = 1 ; i <= S[0] ; i ++ )
{
RMQ[i][j] = RMQ[i][j-1] ;
if ( i + (1 << (j-1)) <= S[0] && P[RMQ[i+(1<<(j-1))][j-1]] < P[RMQ[i][j]] )
RMQ[i][j] = RMQ[i+(1<<(j-1))][j-1] ;
}
}
}

int Find( int l , int r )
{
int k = tab[r-l+1] ;
if ( P[RMQ[l][k]] < P[RMQ[r-(1<<k)+1][k]] )
return RMQ[l][k] ;
return RMQ[r-(1<<k)+1][k] ;
}

int LCA( int x , int y )
{
if ( Fir[x] > Fir[y] )
swap( x , y ) ;
return
S[Find(Fir[x],Fir[y])] ;
}

ll Calc( int x , int y )
{
return Dist[x] + Dist[y] - 2 * Dist[LCA(x,y)] ;
}

Note Merge( Note x , Note y )
{
Note ret = (x.len > y.len ? x : y) ;
if ( Calc(x.a,y.a) > ret.len )
ret = Note( x.a , y.a , Calc(x.a,y.a) ) ;
if ( Calc(x.a,y.b) > ret.len )
ret = Note( x.a , y.b , Calc(x.a,y.b) ) ;
if ( Calc(x.b,y.a) > ret.len )
ret = Note( x.b , y.a , Calc(x.b,y.a) ) ;
if ( Calc(x.b,y.b) > ret.len )
ret = Note( x.b , y.b , Calc(x.b,y.b) ) ;
return ret ;
}

void Build( int v , int l , int r )
{
if ( l == r )
{
T[v].a = T[v].b = D[l] ;
return ;
}
int mid = (l + r) / 2 ;
Build( v + v , l , mid ) ;
Build( v + v + 1 , mid + 1 , r ) ;
T[v] = Merge( T[v+v] , T[v+v+1] ) ;
}

void Search( int v , int l , int r , int x , int y )
{
if ( x > y )
return ;
if ( l == x && r == y )
{
ret = Merge( ret , T[v] ) ;
return ;
}
int mid = (l + r) / 2 ;
if ( y <= mid )
Search( v + v , l , mid , x , y ) ;
else
if ( x > mid )
Search( v + v + 1 , mid + 1 , r , x , y ) ;
else
{
Search( v + v , l , mid , x , mid ) ;
Search( v + v + 1 , mid + 1 , r , mid + 1 , y ) ;
}
}

int main()
{
scanf( "%d" , &n ) ;
for (int i = 1 ; i < n ; i ++ )
{
int u , v , w ;
scanf( "%d%d%d" , &u , &v , &w ) ;
link( u , v , w ) ;
link( v , u , w ) ;
E[++E[0]] = tot ;
}
Dist[1] = 0 ;
Dep[1] = 1 ;
DFS( 1 , 0 ) ;
Pre() ;
// for (int i=1;i<=D[0];i++)
// cout<<D[i]<<" ";
// cout<<endl;
// for (int i=1;i<=n;i++)
// cout<<i<<" "<<DFN[i]<<" "<<R[i]<<endl;
Build( 1 , 1 , n ) ;
for (int i = 1 ; i <= E[0] ; i ++ ) //枚举要删的边
{
int x = Node[E[i]] ;//这条边的左端点
int y = Node[E[i]^1] ;//这个边的右端点
if ( Dep[x] > Dep[y] )
swap( x , y ) ;
ret.a = ret.b = y ;
ret.len = 0 ;
//y是深度大的点，于是从dfs[y]到r[y]这一段
Search( 1 , 1 , n , DFN[y] , R[y] ) ;

ll tp = ret.len ;
ret.a = ret.b = x ;
ret.len = 0 ;
Search( 1 , 1 , n , 1 , DFN[y] - 1 ) ;
//从1到dfn[y]这一段
Search( 1 , 1 , n , R[y] + 1 , n ) ;
//从y出去那一段到n
tp += ret.len ;
ans = max( ans , tp ) ;
}
printf( "%lld " , ans ) ;
return 0 ;
}
/*
8
1 3 1
1 2 1
2 6 1
6 7 1
7 8 1
2 4 1
4 5 1
1 2 4 5 6 7 8 3
1 1 8
2 2 7
3 8 0
4 3 4
5 4 0
6 5 7
7 6 7
8 7 0
6
*/