做题时间：2022.10.10
\(【题目描述】\)
给定一棵 \(n(2\leq n\leq 10^5)\) 个点的带边权的树，有 \(q(q\leq 10^5)\) 次询问，每次询问将树上的一条边 \(d\) 的边权修改为 \(e(e\leq 2\times 10^{13})\)，并询问树的一条直径的边权和。
强制在线。
\(【输入格式】\)
第一行三个整数 \(n,q,w\) 表示点的个数，询问次数及边权上限
接下来 \(n-1\) 行每行三个整数 \((u,v,w)\) 表示树上第一条边
接下来 \(q\) 行，每行两个经过加密的整数 \(d'_j,e'_j\)
解密方式如下：
\(d_j=(d'_j+lst)\mod (n-1)\)
\(e_j=(e'_j+lst) \mod w\)
其中 \(lst\) 表示上一次询问的答案，初值为0
表示将第 \(d_j+1\) 条边的边权修改为 \(e_j\)
\(【输出格式】\)
输出共 \(q\) 行，每行一个整数表示每次修改后的询问的答案
\(【考点】\)
欧拉序、线段树
\(【做法】\)
有点神仙的题目/zhq
每次修改太耗时，可以考虑将原问题进行转化， 使用欧拉序将树上问题转化成序列问题
求解直径即求：
\[\max\{dep_u+dep_v-2\times dep_{lca(u,v)}\} \]这个玩意通过欧拉序转化，设 \(E_i\) 表示欧拉序为 \(i\) 的点，将 \(E_1,E_2,...,E_{2n}\) 看成一个序列，就可以转化。
设 \(v_i=dep[E_i]\)，则：
上柿可以变成：
\[\max\limits_{1\leq l\leq r\leq 2n}\{v_l+v_r-2\times v_{lca}\} \]然后变成：
\[\max\limits_{1\leq l\leq r\leq 2n}\{v_l+v_r-2\times \min\limits_{l\leq k\leq r} v_k\} \]看怎么维护，定义一个 \(ans_k\) 表示答案，pushup的时候考虑左右儿子的合并（一般都是分情况讨论变量在左/右儿子的情况），最优情况下：
- \(l,r\) 同时在左儿子或右儿子，即 \(ans_k=ans_{ls/rs}\)
- \(l,r\) 不在同一个儿子上时，考虑 \(l,k\) 在一个儿子上和 \(r,k\) 在一个儿子上两种情况，这是将原柿子分成了 \(\max\limits_{l\leq k}(v_l-2\times \min v_k)+\max(v_r)\) 和 \(\max(v_l)+\max\limits_{k\leq r}(v_r-2\times \min v_k)\) 两种情况，因此需要一个 \(lmax,rmax,maxn\) 分别记录下上述两个柿子、区间最值。
接下来的问题在于处理 \(lmax\) 和 \(rmax\) ，以 \(lmax\) 为例子，依旧分类讨论，最优情况下：
- \(l,r\) 同时在左儿子或右儿子，即 \(lmax_{k}=lmax_{ls/rs}\)
- \(l,k\) 不在同一个儿子，最有情况肯定是 \(l\) 选左儿子最大，\(k\) 选右儿子最大，即： \(lmax_k=maxn_{ls}-2\times mine_{rs}\)
整理一下，线段树上一共要处理 \(ans,lmax,rmax,maxn,mine\) 共五种变量。
然后看修改操作，修改一条边 \((u,fa_u)\) 的边权为 \(e\)，相当于将以 \(u\) 为根的子树的 \(dep\) 全部加上 \(e-w(u,fa_u)\)，而子树的欧拉序都是连续的，而左右边界正好是 \([L_u,R_u]\)，也就是一个区间修改操作了。
然后就做完力（喜
\(【代码】\)
#include<cstdio>
#include<iomanip>
#define ls(k) k<<1
#define rs(k) k<<1|1
#define int long long
using namespace std;
typedef long long ll;
const int N=2e5+50,inf=1e18;
struct Node{
int maxn,mine,lmax,rmax,tag;
ll ans;
Node(){maxn=lmax=rmax=tag=ans=0,mine=inf;}
#define ans(k) tree[k].ans
#define maxn(k) tree[k].maxn
#define mine(k) tree[k].mine
#define lmax(k) tree[k].lmax
#define rmax(k) tree[k].rmax
#define tag(k) tree[k].tag
}tree[N<<2];
struct edge{
int to,val,nxt;
}a[N<<1];
int head[N],eul[N],L[N],R[N],dep[N],val[N],idx,cnt,n,Q,w;
pair<int,int> q[N];
void add(int u,int v,int w)
{
cnt++;
a[cnt].to=v;
a[cnt].val=w;
a[cnt].nxt=head[u];
head[u]=cnt;
}
void dfs(int u,int fa)//记录欧拉序
{
eul[++idx]=u;
L[u]=idx;
int num=0;
for(int i=head[u];i;i=a[i].nxt){
int v=a[i].to;
if(v!=fa){
dep[v]=dep[u]+a[i].val;
dfs(v,u);
eul[++idx]=u;
q[i]=make_pair(L[v],R[v]);
}
else num=i;
}
R[u]=idx;
q[num]=make_pair(L[u],R[u]);
}
void pushup(Node &k,Node ls,Node rs)
{
k.ans=max(max((ll)ls.lmax+rs.maxn,(ll)rs.rmax+ls.maxn),max(ls.ans,rs.ans));
k.lmax=max(max(ls.lmax,rs.lmax),ls.maxn-2*rs.mine);
k.rmax=max(max(ls.rmax,rs.rmax),rs.maxn-2*ls.mine);
k.maxn=max(ls.maxn,rs.maxn);
k.mine=min(ls.mine,rs.mine);
}
void Add(int k,int l,int r,int v)
{
maxn(k)+=v,mine(k)+=v;
lmax(k)-=v,rmax(k)-=v;
tag(k)+=v;
}
void pushdown(int k,int l,int r)
{
if(!tag(k)) return ;
int mid=(l+r)>>1;
Add(ls(k),l,mid,tag(k)),Add(rs(k),mid+1,r,tag(k));
tag(k)=0;
}
void Modify(int k,int l,int r,int x,int y,int v)
{
if(l>y||r<x) return ;
if(x<=l&&r<=y) return Add(k,l,r,v);
pushdown(k,l,r);
int mid=(l+r)>>1;
if(x<=mid) Modify(ls(k),l,mid,x,y,v);
if(y>mid) Modify(rs(k),mid+1,r,x,y,v);
pushup(tree[k],tree[ls(k)],tree[rs(k)]);
}
Node Query(int k,int l,int r,int x,int y)
{
if(l>y||r<x){Node t;return t;}
if(x<=l&&r<=y) return tree[k];
pushdown(k,l,r);
int mid=(l+r)>>1;
if(x>mid) return Query(rs(k),mid+1,r,x,y);
if(y<=mid) return Query(ls(k),l,mid,x,y);
Node ans;
pushup(ans,Query(ls(k),l,mid,x,y),Query(rs(k),mid+1,r,x,y));
return ans;
}
void Build(int k,int l,int r)
{
if(l==r){
lmax(k)=rmax(k)=-dep[eul[l]];
ans(k)=0,maxn(k)=mine(k)=dep[eul[l]];
return ;
}
int mid=(l+r)>>1;
Build(ls(k),l,mid),Build(rs(k),mid+1,r);
pushup(tree[k],tree[ls(k)],tree[rs(k)]);
}
inline ll Read()
{
ll x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+ch-48;
ch=getchar();
}
return x*f;
}
signed main()
{
n=Read(),Q=Read(),w=Read();
for(int i=1;i<n;i++){
int u=Read(),v=Read(),w=Read();
add(u,v,w),add(v,u,w);
}
dfs(1,0);
Build(1,1,n*2);//注意一下线段树都是[1,2n]的区间
ll lst=0;
while(Q--){
int d=Read(),e=Read();
d=(d+lst)%(n-1)+1;
e=(e+lst)%w;
Modify(1,1,n*2,q[2*d-1].first,q[2*d-1].second,e-a[2*d-1].val);
a[2*d-1].val=e;
lst=Query(1,1,n*2,1,n*2).ans;
printf("%lld\n",lst);
}
return 0;
}