文章目录
- 题目
- 思路
- 代码
Luogu
题目
思路
借鉴这位大佬的：
返回主页liouzhou_101
由于一段连续欧拉序一定是一个连通块，那么区间合并相当于两个连通块相交合并，根据直径性质可知一定是原来端点中的两个
然后根据
dis(u,v)=depu+depv?2?deplca=depu+depv?mineu≤i≤evdepidis(u,v)=dep_u+dep_v-2*dep_{lca}=\\dep_u+dep_v-min_{e_u\le i\le e_v}dep_idis(u,v)=depu?+depv??2?deplca?=depu?+depv??mineu?≤i≤ev??depi?
利用线段树和 STSTST 表快速查询，BIT快速修改
代码
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
LL read(){
LL f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return f*x;
}
#define fi first
#define se second
#define lch (u<<1)
#define rch (u<<1|1)
#define mp make_pair
typedef pair<int,int> pii;
const int MAXN=200000;
const int INF=0x3f3f3f3f;
struct Edge{
int v,nxt;LL w;
}edge[2*MAXN+5];
int ecnt,head[MAXN+5];
void Addedge(int u,int v,LL w){
edge[++ecnt]=(Edge){
v,head[u],w},head[u]=ecnt;edge[++ecnt]=(Edge){
u,head[v],w},head[v]=ecnt;return ;
}
LL val[MAXN+5];
int id[MAXN+5];
int Min[2*MAXN+5][25];
int siz[MAXN+5],dep[MAXN+5];
int dcnt,ocnt,dfn[MAXN+5],ein[MAXN+5],eout[MAXN+5];
void DFS(int u,int fa){
dfn[u]=++dcnt,siz[u]=1;ein[u]=++ocnt,Min[ocnt][0]=u;for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].v;LL w=edge[i].w;if(v==fa) continue;id[i>>1]=v;val[v]=w,dep[v]=dep[u]+1,DFS(v,u);siz[u]+=siz[v],Min[++ocnt][0]=u;}eout[u]=ocnt;return ;
}
LL tr[MAXN+5];
int lowbit(int u){
return u&-u;}
void Add(int i,LL x){
while(i<=dcnt)tr[i]+=x,i+=lowbit(i);return ;
}
LL Sum(int i){
LL ret=0;while(i)ret+=tr[i],i-=lowbit(i);return ret;
}
int lg[2*MAXN+5];
void Init(){
lg[0]=-1;for(int i=1;i<=ocnt;i++)lg[i]=lg[i>>1]+1;for(int j=1;(1<<j)<=ocnt;j++)for(int i=1;i<=ocnt;i++)Min[i][j]=dep[Min[i][j-1]]<dep[Min[i+(1<<(j-1))][j-1]]?Min[i][j-1]:Min[i+(1<<(j-1))][j-1];for(int i=1;i<=dcnt;i++)Add(dfn[i],val[i]),Add(dfn[i]+siz[i],-val[i]);return ;
}
int Lca(int u,int v){
u=ein[u],v=ein[v];if(u>v) swap(u,v);int d=lg[v-u+1];return dep[Min[u][d]]<dep[Min[v-(1<<d)+1][d]]?Min[u][d]:Min[v-(1<<d)+1][d];
}
LL dis(int u,int v){
return Sum(dfn[u])+Sum(dfn[v])-2*Sum(dfn[Lca(u,v)]);}
struct node{
int u,v;LL d;friend bool operator < (node a,node b){
return a.d<b.d;}friend node operator + (node a,node b){
return max(max(a,b),max(max((node){
a.u,b.v,dis(a.u,b.v)},(node){
a.v,b.u,dis(a.v,b.u)}),max((node){
a.u,b.u,dis(a.u,b.u)},(node){
a.v,b.v,dis(a.v,b.v)})));}
}tree[8*MAXN+5];
void Build(int u,int L,int R){
if(L==R){
tree[u]=(node){
Min[L][0],Min[L][0],0};return ;}int Mid=(L+R)>>1;Build(lch,L,Mid),Build(rch,Mid+1,R);tree[u]=tree[lch]+tree[rch];return ;
}
void Modi(int u,int L,int R,int qL,int qR){
if(qL<=L&&R<=qR)return ;int Mid=(L+R)>>1;if(qL<=Mid) Modi(lch,L,Mid,qL,qR);if(Mid+1<=qR) Modi(rch,Mid+1,R,qL,qR);tree[u]=tree[lch]+tree[rch];return ;
}
int main(){
int n=read(),q=read();LL W=read();ecnt=1;for(int i=1;i<n;i++){
int u=read(),v=read();LL w=read();Addedge(u,v,w);}DFS(2,0);Init();Build(1,1,ocnt);LL lst=0;for(int i=1;i<=q;i++){
int d=(read()+lst)%(n-1)+1;LL e=(read()+lst)%W;int u=id[d];Add(dfn[u],e-val[u]),Add(dfn[u]+siz[u],-(e-val[u]));Modi(1,1,ocnt,ein[u],eout[u]);printf("%lld\n",tree[1].d);lst=tree[1].d;val[u]=e;}return 0;
}
/* 6 5 14 1 2 2 3 3 4 2 4 5 6 2 0 4 2 2 1 6 2 3 4 3 2 6 3 4 2 5 4 6 2 1 1 2 1 2*/