动态维护树的直径

打2019ICPC上海网络赛的时候，碰到了一道题(A)，可以转化成动态维护树的直径的模型。但是由于不会写，就想要学习该算法，发现方法还多，一点一点学把。

首先是例题：https://nanti.jisuanke.com/t/41398

方法一：最容易理解和暴力的方法(树剖LCA+线段树)

树剖维护树的LCA，线段树合并时维护树的直径。

思路：

1.首先要会树剖，用树剖处理该树，得到一个线段树维护的DFS序(其实就是树剖)。

2.建立一颗线段树，区间[l,r]表示包含点l,r中间的所有点对的最长直径，同时维护直径的两端点。

关键就在于维护直径和直径的两端点。就在于线段树合并。

合并的时候，采取最暴力4次比较，即：左子树会有一个直径，右子树会有一个直径，分别是四个点，分别比较四个点之间的LCA，同时获得最长的直径。O(4*long n)。

查询的时候，整棵树的直径，就是维护直径的线段树的跟所表示的(x,y)和l。

注意，这个方法复杂度较大，跑1e5的数据(1e5个点，1e5次查询)需要的时间大概是4000+ms左右，如果常数优化可能会快一点，但是估计很有限,所以如果时间在1000ms的话，估计只能处理1e4的数据量了。

(这个是没有常数优化的)

下面就是代码了，写的可能比较乱(一开始用的类，结果反而麻烦了QAQ)

但是个人感觉还是比较清楚的，两个类实现的两个功能：第一个是树剖动态维护LCA。第二个是线段树动态维护树的直径。

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand((unsigned)time(NULL));rand();

#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
 
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
      
const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=998244353;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)

/*
首先维护树的直径。
DFS序+线段树可求出LCA距离。
对于每次更新，点下方的所有点都要更新。
查找时，找到树的直径，比较两端点的距离 
*/
struct Edge1{
	int v,val,nxt;
	Edge1(int _v=0,int _val=0,int _nxt=0){
		v=_v;val=_val;nxt=_nxt;
	}
};
Edge1 Edge[MAXN<<2];
int Head[MAXN],Ecnt;
struct TreeCut{//树剖 
	int Deep[MAXN],Fa[MAXN],Size[MAXN],Son[MAXN];
	int Idx[MAXN],RIdx[MAXN],Icnt;
	int Top[MAXN];
	int A[MAXN],B[MAXN];
	
	int DFS1(int u,int fa,int dep){
		Deep[u]=dep;Fa[u]=fa;Size[u]=1;
		int maxson=-1;
		for(int i=Head[u];i+1;i=Edge[i].nxt){
			int v=Edge[i].v;
			if(v==fa) continue ;
			Size[u]+=DFS1(v,u,dep+1);
			if(Size[v]>maxson){
				maxson=Size[v];
				Son[u]=v;
			}
		}return Size[u];
	}
	void DFS2(int u,int topfa){
		Idx[u]=++Icnt;RIdx[Icnt]=u;B[Idx[u]]=A[u];Top[u]=topfa;
		if(Son[u]==-1) return ;
		DFS2(Son[u],topfa);
		for(int i=Head[u];i+1;i=Edge[i].nxt){
			int v=Edge[i].v;
			if(Idx[v]==0) DFS2(v,v);
		}
	}
	
	struct Node{
		int l,r,len;
		ll sum;
	};
	Node Tree[MAXN<<2];
	
	void PushUp(int rt){
		Tree[rt].sum=Tree[rt<<1].sum+Tree[rt<<1|1].sum;
	}
	void Build(int l,int r,int rt){
		Tree[rt].l=l;Tree[rt].r=r;Tree[rt].len=r-l+1;
		if(l==r){
			Tree[rt].sum=B[l];
			return ;
		}int mid=(l+r)>>1;
		Build(l,mid,rt<<1);Build(mid+1,r,rt<<1|1);
		PushUp(rt);
	}
	void Update(int pos,int val,int rt){
		if(Tree[rt].l==Tree[rt].r){
			Tree[rt].sum=val;
			return ;
		}
		if(Tree[rt<<1].r>=pos) Update(pos,val,rt<<1);
		else Update(pos,val,rt<<1|1);
		PushUp(rt);
	}
	ll Query(int ql,int qr,int rt){
		if(ql<=Tree[rt].l&&Tree[rt].r<=qr) return Tree[rt].sum;
		if(ql>=Tree[rt<<1|1].l) return Query(ql,qr,rt<<1|1);
		else if(qr<=Tree[rt<<1].r) return Query(ql,qr,rt<<1);
		else{
			return Query(ql,qr,rt<<1)+Query(ql,qr,rt<<1|1);
		}
	}
	ll QueryLCA(int l,int r){//得到[l~r]的距离 
		ll ans=0;
		while(Top[l]!=Top[r]){
			if(Deep[Top[l]]<Deep[Top[r]]) swap(l,r);
			ans+=Query(Idx[Top[l]],Idx[l],1);
			l=Fa[Top[l]];
		}
		if(Deep[l]>Deep[r]) swap(l,r);
		ans+=Query(Idx[l],Idx[r],1);ans-=Query(Idx[l],Idx[l],1);
		return ans;
	}
	void Show(int rt){
		printf("l=%d r=%d sum=%lld\n",Tree[rt].l,Tree[rt].r,Tree[rt].sum);
		if(Tree[rt].l==Tree[rt].r) return ;
		Show(rt<<1);Show(rt<<1|1);
	}
};
TreeCut LCA;
struct TreeDia{//维护树的直径 
	struct Node{
		int l,r,len;
		int x,y;
		ll dis;
		Node(int _x=0,int _y=0,ll _dis=0){
			x=_x;y=_y;dis=_dis;
		}
	};
	Node Tree[MAXN<<2];
	
	void PushUp(int rt){
		Tree[rt]=Tree[rt<<1].dis>Tree[rt<<1|1].dis?Tree[rt<<1]:Tree[rt<<1|1];
		int x1=Tree[rt<<1].x,y1=Tree[rt<<1].y,x2=Tree[rt<<1|1].x,y2=Tree[rt<<1|1].y;
		ll ans;int l=Tree[rt<<1].l,r=Tree[rt<<1|1].r;
		if((ans=LCA.QueryLCA(x1,x2))>Tree[rt].dis) Tree[rt]=Node(x1,x2,ans);
		if((ans=LCA.QueryLCA(x1,y2))>Tree[rt].dis) Tree[rt]=Node(x1,y2,ans);
		if((ans=LCA.QueryLCA(y1,x2))>Tree[rt].dis) Tree[rt]=Node(y1,x2,ans);
		if((ans=LCA.QueryLCA(y1,y2))>Tree[rt].dis) Tree[rt]=Node(y1,y2,ans);
		Tree[rt].l=l;Tree[rt].r=r;
	}
	void Build(int l,int r,int rt){
		Tree[rt].l=l;Tree[rt].r=r;Tree[rt].len=r-l+1;
		if(l==r){
			Tree[rt].x=Tree[rt].y=LCA.RIdx[l];
			Tree[rt].dis=0;
			return ;
		}int mid=(l+r)>>1;
		Build(l,mid,rt<<1);Build(mid+1,r,rt<<1|1);
		PushUp(rt);
	}
	void Update(int ql,int qr,int rt){
		if(ql<=Tree[rt].l&&Tree[rt].r<=qr) return ;
		if(ql>=Tree[rt<<1|1].l) Update(ql,qr,rt<<1|1);
		else if(qr<=Tree[rt<<1].r) Update(ql,qr,rt<<1);
		else{
			Update(ql,qr,rt<<1);Update(ql,qr,rt<<1|1);
		}PushUp(rt);
	}
	void Show(int rt){
		printf("l=%d r=%d x=%d y=%d dis=%lld\n",Tree[rt].l,Tree[rt].r,Tree[rt].x,Tree[rt].y,Tree[rt].dis);
		if(Tree[rt].l==Tree[rt].r) return ;
		Show(rt<<1);Show(rt<<1|1);
	}
};
TreeDia Dia;
int U[MAXN],V[MAXN],Val[MAXN];
int n,m;

void Intt(){
	clean(Head,-1);Ecnt=0;
	clean(LCA.Deep,0);clean(LCA.Fa,-1);clean(LCA.Size,0);clean(LCA.Son,-1);
	LCA.Icnt=0;
}
void AddEdge(int u,int v,int val){
	Edge[Ecnt]=Edge1(v,val,Head[u]);
	Head[u]=Ecnt++;
}
int main(){
	Intt();
	scanf("%d",&n);
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&U[i],&V[i],&Val[i]);
		AddEdge(U[i],V[i],Val[i]);AddEdge(V[i],U[i],Val[i]);
	}
	LCA.DFS1(1,-1,1);//找出深度 
	for(int i=1;i<n;++i){//按深度进行赋值，边权跑到点权上 
		int u=U[i],v=V[i],val=Val[i];
		if(LCA.Deep[u]>LCA.Deep[v]) LCA.A[u]=Val[i];
		else LCA.A[v]=Val[i];
	}LCA.DFS2(1,1);//获得DFS序 
	LCA.Build(1,n,1);//对DFS序进行剖分 
	Dia.Build(1,n,1);//获得初始的序列 
	scanf("%d",&m);
	for(int i=1;i<=m;++i){
		char opt[5];scanf("%s",opt+1);
		if(opt[1]=='Q'){
			int x;scanf("%d",&x); 
			int u=Dia.Tree[1].x,v=Dia.Tree[1].y;
			ll dis1=LCA.QueryLCA(u,x),dis2=LCA.QueryLCA(v,x);
			printf("%lld\n",max(dis1,dis2));
		}
		else{
			int x,val;scanf("%d%d",&x,&val);
			int u=U[x],v=V[x];
			if(LCA.Deep[u]>LCA.Deep[v]) swap(u,v);
			LCA.Update(LCA.Idx[v],val,1);//维护更新后的LCA 
			Dia.Update(LCA.Idx[v],LCA.Idx[v]+LCA.Size[v]-1,1);//同时维护直径线段树 
		}
	}
}

/*
5
1 2 1
1 3 1
2 4 1
2 5 1
3
Q 1
C 1 2
Q 2
*/