<div class="solution-view">
    <div class="row">
        <div class="col-md-6">
            <p>提交时间：2024-10-16 13:20:05</p>
        </div>
        <div class="col-md-6">
            <p>运行 ID: <a href="/solution/detail?id=33617">33617</a></p>
        </div>
    </div>
    <div class="pre"><p>#include&lt;bits/stdc++.h&gt;
using namespace std;
#define int long long
int op;
int n,q,k=100,id;
inline void decode(int &amp;l,int &amp;r,int &amp;k,int lstans) {
    lstans%=19260817;
    if(op){
        l^=lstans;l=(l%n+n)%n+1;
        r^=lstans;r=(r%n+n)%n+1;
        if(l&gt;r)swap(l,r);
        k^=lstans;
        k=(k%min(r-l+1,100ll))+1;
    }
}
int per[200300];
#define pii pair&lt;int,int&gt;
#define p1(x) x.first
#define p2(x) x.second
int dfn[200300],tk;
vector&lt;pii&gt;g[200300],G[200300];
int siz[200300],fa[200300],hs[200300];
int tp[200300],dep[200300],d[200300];
inline void dfs(int u){
    siz[u]=1;
    dep[u]=dep[fa[u]]+1;
    for(pii e:g[u])if(p1(e)!=fa[u]){
        int v=p1(e),c=p2(e);
        fa[v]=u;
        d[v]=d[u]+c;
        dfs(v);
        siz[u]+=siz[v];
        if(siz[v]&gt;siz[hs[u]])hs[u]=v;
    }
}
inline void dfs2(int u,int t){
    tp[u]=t;
    dfn[u]=++tk;
    if(hs[u])dfs2(hs[u],t);
    for(pii e:g[u])if(p1(e)!=fa[u]&amp;&amp;p1(e)!=hs[u])
        dfs2(p1(e),p1(e));
}
inline int LCA(int u,int v){
    while(tp[u]!=tp[v]){
        if(dep[tp[u]]&lt;dep[tp[v]])swap(u,v);
        u=fa[tp[u]];
    }
    if(dep[u]&lt;dep[v])return u;
    return v;
}
inline int dis(int u,int v){
    return d[u]+d[v]-2*d[LCA(u,v)];
}
inline bool cmp(int x,int y){
    return dfn[x]&lt;dfn[y];
}
inline void bd_xt(vector&lt;int&gt;&amp;A){
    sort(A.begin(),A.end(),cmp);
    int k=A.size();
    for(int i=0;i+1&lt;k;i++)
        A.emplace_back(LCA(A[i],A[i+1]));
    vector&lt;int&gt;U;
    sort(A.begin(),A.end(),cmp);
    k=A.size();
    for(int i=0;i&lt;k;i++)
        if(U.empty()||U.back()!=A[i])U.emplace_back(A[i]);
    for(int x:U)G[x].clear();
    int lst=0;
    for(int x:U){
        if(lst){
            int L=LCA(x,lst);
            int c=d[x]-d[L];
            G[L].push_back({x,c});
            G[x].push_back({L,c});
        }
        lst=x;
    }
}   
int p[200030];
vector&lt;int&gt;LF;
inline bool cmpL(int x,int y){
    return p[x]&gt;p[y];
}
int ls[200300],lsw[200300];
inline int dfs(int u,int f,int d){
    int mx=d;
    ls[u]=0;
    lsw[u]=0;
    for(pii e:G[u])if(p1(e)!=f){
        int v=p1(e),c=p2(e);
        int w=dfs(v,u,d+c);
        if(w&gt;mx){ls[u]=v;mx=w;lsw[u]=c;}
    }
    
    // cout&lt;&lt;u&lt;&lt;&quot; &quot;&lt;&lt;ls[u]&lt;&lt;&quot; &quot;&lt;&lt;f&lt;&lt;endl;
    if(!ls[u]&amp;&amp;f)LF.push_back(u);
    return mx;
}
inline void dfs2(int u,int f,int d){

    if(ls[u])dfs2(ls[u],u,d+lsw[u]);
    else p[u]=d;
    for(pii e:G[u])if(p1(e)!=f&amp;&amp;p1(e)!=ls[u])
        dfs2(p1(e),u,p2(e));
}

inline void calL(int u){
    LF.clear();
    dfs(u,0,0);
    dfs2(u,0,0);
    sort(LF.begin(),LF.end(),cmpL);
}
struct node{
    int x,y;
    vector&lt;int&gt;w,X;
    friend node operator +(const node A,const node B){
        vector&lt;int&gt;NW=A.X;
        for(int x:B.X)NW.emplace_back(x);
        bd_xt(NW);
        int x=0,y=0,len=0;
        int w=dis(A.x,A.y);
        if(w&gt;len)x=A.x,y=A.y,len=w;
        w=dis(A.x,B.x);
        if(w&gt;len)x=A.x,y=B.x,len=w;
        w=dis(A.x,B.y);
        if(w&gt;len)x=A.x,y=B.y,len=w;
        w=dis(A.y,B.x);
        if(w&gt;len)x=A.y,y=B.x,len=w;
        w=dis(A.y,B.y);
        if(w&gt;len)x=A.y,y=B.y,len=w;
        w=dis(B.x,B.y);
        if(w&gt;len)x=B.x,y=B.y,len=w;
        calL(x);
        int k=min(100ll,(int)LF.size());
        vector&lt;int&gt;W(k+1),X(k+1);
        W[0]=0,X[0]=x;
        // W.emplace_back(0);
        // X.emplace_back(x);
        // cout&lt;&lt;LF.size()&lt;&lt;&quot; &quot;&lt;&lt;x&lt;&lt;&quot; &quot;&lt;&lt;y&lt;&lt;endl;
        // cout&lt;&lt;x&lt;&lt;&quot; &quot;&lt;&lt;y&lt;&lt;&quot; &quot;&lt;&lt;A.w.size()&lt;&lt;&quot; &quot;&lt;&lt;B.w.size()&lt;&lt;&quot; &quot;&lt;&lt;LF.size()&lt;&lt;endl;
        // cout&lt;&lt;&quot;!&quot;;
        // for(int x:A.X)cout&lt;&lt;x&lt;&lt;&quot; &quot;;
        // cout&lt;&lt;endl;
        // for(int x:B.X)cout&lt;&lt;x&lt;&lt;&quot; &quot;;
        // cout&lt;&lt;endl;
        // cout&lt;&lt;endl;
        // cout&lt;&lt;endl;
        for(int i=0;i&lt;k;i++){
            X[i+1]=LF[i];
            W[i+1]=W[i]+p[LF[i]];
            // X.emplace_back(LF[i]);
            // W.emplace_back(W.back()+p[LF[i]]);
        }
        return {x,y,W,X};
    }
}T[200300&lt;&lt;2];
#define lc(x) (x&lt;&lt;1)
#define rc(x) (x&lt;&lt;1|1)
inline void bd(int x,int l,int r){
    if(l==r){
        T[x]={per[l],per[l],{0},{per[l]}};
        return ;
    }   
    int mid=l+r&gt;&gt;1;
    bd(lc(x),l,mid);
    bd(rc(x),mid+1,r);
    T[x]=T[lc(x)]+T[rc(x)];
    // cout&lt;&lt;l&lt;&lt;&quot; &quot;&lt;&lt;r&lt;&lt;&quot; &quot;&lt;&lt;T[x].w.size()&lt;&lt;&quot; &quot;&lt;&lt;T[x].X.size()&lt;&lt;&quot; &quot;&lt;&lt;T[x].x&lt;&lt;&quot; &quot;&lt;&lt;T[x].y&lt;&lt;endl;
}
inline node gt(int x,int l,int r,int L,int R){
    if(L&lt;=l&amp;&amp;r&lt;=R)return T[x];
    int mid=l+r&gt;&gt;1;
    if(R&lt;=mid)return gt(lc(x),l,mid,L,R);
    if(L&gt;mid)return gt(rc(x),mid+1,r,L,R);
    return gt(lc(x),l,mid,L,R)+gt(rc(x),mid+1,r,L,R);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    // int CC=clock();
    // freopen(&quot;d.in&quot;,&quot;r&quot;,stdin);
    // freopen(&quot;d.out&quot;,&quot;w&quot;,stdout);
    cin&gt;&gt;id&gt;&gt;op;
    cin&gt;&gt;n;
    
    for(int i=1;i&lt;n;i++){
        int u,v,w;
        cin&gt;&gt;u&gt;&gt;v&gt;&gt;w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dfs(1);
    dfs2(1,1);
    for(int i=1;i&lt;=n;i++)
    cin&gt;&gt;per[i];
    // for(int i=1;i&lt;=n;i++)
    // cout&lt;&lt;i&lt;&lt;&quot; &quot;&lt;&lt;dfn[i]&lt;&lt;&quot; &quot;&lt;&lt;tp[i]&lt;&lt;&quot; &quot;&lt;&lt;hs[i]&lt;&lt;endl;
    bd(1,1,n);
    // return 0;
    cin&gt;&gt;q;
    int lst=0;
    // cout&lt;&lt;&quot;-----------&quot;&lt;&lt;endl;
    // cerr&lt;&lt;(clock()-CC)*1000/CLOCKS_PER_SEC&lt;&lt;endl;
    while(q--){
        int l,r,k;
        cin&gt;&gt;l&gt;&gt;r&gt;&gt;k;
        decode(l,r,k,lst);
        node A=gt(1,1,n,l,r);
        lst=A.w[min(k-1,(int)A.w.size()-1)];
        // for(int x:A.X)cout&lt;&lt;x&lt;&lt;&quot; &quot;;
        // cout&lt;&lt;endl;
        // for(int w:A.w)cout&lt;&lt;w&lt;&lt;&quot; &quot;;
        // cout&lt;&lt;endl;
        // cout&lt;&lt;A.x&lt;&lt;&quot; &quot;&lt;&lt;A.y&lt;&lt;endl;
        cout&lt;&lt;lst&lt;&lt;&quot;\n&quot;;
        // cout&lt;&lt;endl;
        // return 0;
    }
    // cerr&lt;&lt;(clock()-CC)*1000/CLOCKS_PER_SEC&lt;&lt;endl;
    // cerr&lt;&lt;ct&lt;&lt;endl;
    cout.flush();
    return 0;
}</p></div>
</div>
<script type="text/javascript">
    (function ($) {
        $(document).ready(function () {
            $('.pre p').each(function(i, block) {  // use <pre><p>
                hljs.highlightBlock(block);
            });
        })
    })(jQuery);
</script>