CF1192B Dynamic Diameter（LCT）

$\text{Foreword}$

@zhengrunzhe 大佬的矩阵做法过于神奇，蒟蒻无法理解…
欧拉序的做法确实非常巧妙，但我也想不到这么神仙的做法…
提供一种可能简单一些的 LCT 做法。
由于本人 LCT 无法像大佬那么神，讲的会比较详细一些，也许对其他 LCT 平民玩家更加友好？

$\text{Solution}$

本题有一个很关键的性质：边权非负。（欧拉序的做法也要基于这个性质）
又发现修改无非改大/小，在/不在原直径上，利用非负的性质分别讨论一下，就会发现新直径至少有一个节点和原来相同。
所以我们一开始暴力求出直径后，只需要不断把原直径的两端点提出来，用从二者出发新的最长路径来尝试作为新直径就行了。
所以现在只需要动态维护从一个点出发的最长路径。

常规套路，先边化点，边权化点权。
设 $w_x$ 表示 $x$ 的点权，$su{m}_x$ 表示 $x$ splay子树内点权之和，$di{s}_x$ 表示从 $x$ 所在 splay 子树内深度最浅的节点出发往子树延伸的最长路径。
先不考虑 $x$ 实链父亲，尝试求出从 $x$ 出发往子树延伸的最长路径 $re{s}_x$。

一开始有：
$$re{s}_x=w_x$$
对于 $x$ 的虚儿子，对每个节点开一个 std::set 维护虚子树，进行转移：
$$re{s}_x\leftarrow \underset{son}{\max }di{s}_{son}+w_x$$
还有从 $x$ 的实儿子转移，不难发现其对应的就是 $di{s}_{r{s}_x}$：
$$re{s}_x\leftarrow di{s}_{r{s}_x}+w_x$$
求完 $re{s}_x$ 后，如果 $x$ 没有左儿子，说明他就是链头，直接让 $di{s}_x=re{s}_x$ 即可；否则，链头可以不使用 $re{s}_x$ 的转移，或者使用 $re{s}_x$ 的转移，那么还要加上 $x$ 到链头一段的权值和，分别对应 max 的前后两项：
$$di{s}_x=\max (di{s}_{l{s}_x},re{s}_x+su{m}_{l{s}_x})$$

这样就做完了。由于转移不对称，所以我们还要镜像的处理一个 $di{s}^{\prime }x$，在翻转时直接交换两项即可。

$\text{Code}$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
using namespace std;

const int N=2e5+100;
inline ll read(){
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}

int n,m;


#define pr pair<ll,int>
#define mkp make_pair
pr operator + (const pr &o,const ll &w){return mkp(o.first+w,o.second);}

int tr[N][2],rev[N],f[N];
ll sum[N],w[N];
pr dis1[N],dis2[N];
multiset<pr>s[N];
#define ls(x) tr[x][0]
#define rs(x) tr[x][1]
inline bool nroot(int x){return ls(f[x])==x||rs(f[x])==x;}
inline bool which(int x){return rs(f[x])==x;}

inline void pushup(int x){
  sum[x]=w[x]+sum[ls(x)]+sum[rs(x)];
  
  dis1[x]=s[x].empty()?mkp(w[x],x<=n?x:-1):(*s[x].rbegin())+w[x];
  if(rs(x)) dis1[x]=max(dis1[x],dis1[rs(x)]+w[x]);
  if(ls(x)) dis1[x]=max(dis1[ls(x)],dis1[x]+sum[ls(x)]);
  
  dis2[x]=s[x].empty()?mkp(w[x],x<=n?x:-1):(*s[x].rbegin())+w[x];
  if(ls(x)) dis2[x]=max(dis2[x],dis2[ls(x)]+w[x]);
  if(rs(x)) dis2[x]=max(dis2[rs(x)],dis2[x]+sum[rs(x)]);
  
  return;
}
inline void Rev(int x){
  if(x){
    rev[x]^=1;
    swap(ls(x),rs(x));
    swap(dis1[x],dis2[x]);
  }
  return;
}
inline void pushdown(int x){
  if(rev[x]){
    rev[x]=0;
    Rev(ls(x));
    Rev(rs(x));
  }
  return;
}
void dfs(int x){
  if(!x) return;
  pushdown(x);
  debug("x=%d f=%d ls=%d rs=%d w=%lld dis1=(%lld %d) s: ",x,f[x],ls(x),rs(x),w[x],dis1[x].first,dis1[x].second);
  for(pr o:s[x]) debug("(%lld %d) ",o.first,o.second);
  debug("\n");
  dfs(ls(x));dfs(rs(x));
}
void print(){
  for(int i=1;i<=n+n-1;i++){
    if(!nroot(i)) dfs(i);
  }
}
inline void rotate(int x){
  int fa=f[x],gfa=f[fa];
  int d=which(x),son=tr[x][d^1];
  f[x]=gfa;if(nroot(fa)) tr[gfa][which(fa)]=x;
  f[fa]=x;tr[x][d^1]=fa;
  if(son) {f[son]=fa;}tr[fa][d]=son;
  pushup(fa);pushup(x);
  return;
}
int zhan[N];
inline void splay(int x){
  int top=0,y=x;
  zhan[++top]=y;
  while(nroot(y)) zhan[++top]=y=f[y];
  while(top) pushdown(zhan[top--]);
  for(int fa;fa=f[x],nroot(x);rotate(x)){
    if(nroot(fa)) which(fa)==which(x)?rotate(fa):rotate(x);
  }
  return;
}
inline void access(int x){
  for(int y=0;x;y=x,x=f[x]){
    splay(x);
    if(rs(x)){
      s[x].insert(dis1[rs(x)]);
    }
    if(y){
      s[x].erase(s[x].find(dis1[y]));
    }
    rs(x)=y;
    pushup(x);
  }
  return;
}
inline void makeroot(int x){
  access(x);splay(x);Rev(x);
}
inline void link(int x,int y){
  makeroot(x);makeroot(y);
  f[x]=y;
  s[y].insert(dis1[x]);
  pushup(y);
  return;
}

ll mod;
ll D;
int a,b;
signed main(){
  #ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
  #endif
  n=read();m=read();mod=read();
  for(int i=1;i<n;i++){
    int x=read(),y=read();
    w[n+i]=read();
    link(x,n+i);
    link(y,n+i);
  }
  for(int i=1;i<=n;i++){
    makeroot(i);
    if(dis1[i].first>D){
      D=dis1[i].first;
      a=i;b=dis1[i].second;
    }
  }
  ll lst=0;
  while(m--){
    ll x=(read()+lst)%(n-1)+1 +n,ww=(read()+lst)%mod;    
    makeroot(x);
    w[x]=ww;pushup(x);
    int u=a,v=b;
    D=a=b=0;

    makeroot(u);
    if(dis1[u].first>=D){
      D=dis1[u].first;
      a=u;b=dis1[u].second;
    }
    
    makeroot(v);
    if(dis1[v].first>=D){
      D=dis1[v].first;
      a=v;b=dis1[v].second;
    }

    printf("%lld\n",lst=D);
  }
  return 0;
}
/*
*/