提交时间:2024-10-16 15:55:20
运行 ID: 33624
#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair typedef long long ll; typedef unsigned long long ull; using namespace std; const int maxn=2e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,op,P[maxn],dfn[maxn],siz[maxn],ct;ll lst; vector<pi>v[maxn]; int fa[maxn][20],dep[maxn]; ll dis[maxn]; void dfs(int u){ dep[u]=dep[fa[u][0]]+1,dfn[u]=++ct,siz[u]=1; for(auto it:v[u]){ int x=it.p1,w=it.p2; if(!(x^fa[u][0]))continue; fa[x][0]=u;dis[x]=dis[u]+w;dfs(x); siz[u]+=siz[x]; } } int lca(int x,int y){ if(dep[x]>dep[y])swap(x,y); down(i,19,0)if(dep[fa[y][i]]>=dep[x])y=fa[y][i]; if(x==y)return x; down(i,19,0)if(fa[x][i]^fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; } ll g(int x,int y){ return dis[x]+dis[y]-2*dis[lca(x,y)]; } void dec(int &l,int &r,int &k){ l=read(),r=read(),k=read(); if(op){ lst%=19260817; l^=lst,r^=lst;l=(l%n+n)%n+1;r=(r%n+n)%n+1; if(l>r)swap(l,r); k^=lst;k=k%min(r-l+1,100)+1; } } vector<pair<int,ll> >vec[maxn]; int en[maxn],son[maxn],top[maxn]; ll mxd[maxn],W[maxn]; void DFS(int u,int ff){ if(!ff)W[u]=0; son[u]=0,mxd[u]=0; for(auto it:vec[u]){ int x=it.p1;ll w=it.p2; if(x==ff)continue; W[it.p1]=w; DFS(it.p1,u);w+=mxd[it.p1]; if(w>mxd[u])mxd[u]=w,son[u]=it.p1; } } void DFS2(int u,int tp,int ff){ en[tp]=u;top[u]=tp; for(auto it:vec[u]){ int x=it.p1; if(x==ff)continue; if(x==son[u])DFS2(x,tp,u); else DFS2(x,x,u); } } struct nd { int x,y;ll w; vector<int>S; }; void UQ(vector<int>&A){ //for(int x:A)cout<<x<<" ";cout<<endl; vector<int>B;int lst=-1; for(int x:A)if(x!=lst)lst=x,B.p_b(x); A.swap(B); //for(int x:A)cout<<x<<" ";cout<<endl; } void lk(int a,int b,ll w){ vec[a].p_b(m_p(b,w)); vec[b].p_b(m_p(a,w)); } nd operator+(nd a,nd b){ //cout<<"MERGE"<<endl; //cout<<a.x<<" ";for(int x:a.S)cout<<x<<" ";cout<<endl; //cout<<b.x<<" ";for(int x:b.S)cout<<x<<" ";cout<<endl; nd c; if(a.w<b.w)c=b;else c=a;c.S.clear(); if(dis[a.x]+dis[b.x]>c.w){ ll w=g(a.x,b.x); if(w>c.w)c.w=w,c.x=a.x,c.y=b.x; } if(dis[a.x]+dis[b.y]>c.w){ ll w=g(a.x,b.y); if(w>c.w)c.w=w,c.x=a.x,c.y=b.y; } if(dis[a.y]+dis[b.x]>c.w){ ll w=g(a.y,b.x); if(w>c.w)c.w=w,c.x=a.y,c.y=b.x; } if(dis[a.y]+dis[b.y]>c.w){ ll w=g(a.y,b.y); if(w>c.w)c.w=w,c.x=a.y,c.y=b.y; } vector<int>T;T.p_b(a.x),T.p_b(b.x); for(int x:a.S)T.p_b(x);for(int x:b.S)T.p_b(x); auto cmp=[](int x,int y){ return dfn[x]<dfn[y]; }; sort(T.begin(),T.end(),cmp); UQ(T); vector<int>A;int sz=T.size(); up(i,0,sz-2)A.p_b(lca(T[i],T[i+1])); for(int x:T)A.p_b(x);T.swap(A); //cout<<"!! "<<endl; //for(int x:T)cout<<x<<" ";cout<<endl; sort(T.begin(),T.end(),cmp); UQ(T); vector<pair<pi,ll> >G;sz=T.size(); up(i,0,sz-2){ int u=lca(T[i],T[i+1]),x=T[i+1]; G.p_b(m_p(m_p(u,x),g(u,x))); }for(auto it:G)vec[it.p1.p1].clear(),vec[it.p1.p2].clear(); for(auto it:G)/*cout<<"EDGE "<<it.p1.p1<<" "<<it.p1.p2<<endl,*/lk(it.p1.p1,it.p1.p2,it.p2); DFS(c.x,0);DFS2(c.x,c.x,0); auto cmp2=[](int x,int y){ return mxd[top[x]]+W[top[x]]>mxd[top[y]]+W[top[y]]; };A.clear(); //if(a.x==8&&a.y==8&&b.x==6&&b.y==6)cout<<"! "<<top[6]<<" "<<en[8]<<endl; for(int x:T)if(en[top[x]]==x)A.p_b(x); sort(A.begin(),A.end(),cmp2);UQ(A); T.clear();for(int x:A)if(x!=c.x)T.p_b(x);A.swap(T); sz=min((int)A.size(),100); up(i,0,sz-1)c.S.p_b(A[i]); //cout<<"now"<<endl; //cout<<c.x<<" ";for(int x:c.S)cout<<x<<" ";cout<<endl; return c; } struct SegTree { nd T[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) void pu(int p){T[p]=T[ls(p)]+T[rs(p)];} void bd(int l,int r,int p){ if(l==r){ T[p].x=T[p].y=P[l]; T[p].S.p_b(P[l]);return; }int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p));pu(p); }nd qry(int l,int r,int s,int t,int p){ if(l<=s&&t<=r)return T[p]; int mid=s+t>>1; if(r<=mid)return qry(l,r,s,mid,ls(p)); if(l>mid)return qry(l,r,mid+1,t,rs(p)); return qry(l,r,s,mid,ls(p))+qry(l,r,mid+1,t,rs(p)); } }T; ll qry(int l,int r,int k){ nd w=T.qry(l,r,1,n,1); vector<int>A;A.p_b(w.x); k--;k=min(k,(int)w.S.size());up(i,0,k-1)A.p_b(w.S[i]);k=A.size(); auto cmp=[](int x,int y){ return dfn[x]<dfn[y]; }; sort(A.begin(),A.end(),cmp); ll all=0;for(int x:A)all+=dis[x]; up(i,0,k-1)all-=dis[lca(A[i],A[(i+1)%k])]; return all; } void slv(){ int id=read(); op=read(),n=read(); up(i,1,n-1){ int x=read(),y=read(),w=read(); v[x].p_b(m_p(y,w)),v[y].p_b(m_p(x,w)); }dfs(1); up(i,1,19)up(j,1,n)fa[j][i]=fa[fa[j][i-1]][i-1]; up(i,1,n)P[i]=read(); T.bd(1,n,1); int q=read(),l=0,r=0,k=0; while(q--){ dec(l,r,k); lst=qry(l,r,k); printf("%lld\n",lst); } }int main(){ //freopen("d.in","r",stdin); //freopen("d.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }