【BZOJ5415&UOJ393】归程（Kruskal重构树，最短路）

题意：From https://www.cnblogs.com/Memory-of-winter/p/11628351.html

思路：先从1开始跑一遍dijkstra，建出kruskal重构树之后每个叶子结点的权值为它到1的距离

询问等价于从v开始只要倍增的点的权值>p就往上跳，这样跳到某个点u之后询问u的子树中叶子结点最小的权值

因为是静态的，实际上可以不把kruskal实际建出来，只要维护倍增数组和子树中最小值即可

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef long double ld;

 typedef pair<int,int> PII;

 typedef pair<ll,int> Pli;

 typedef pair<ll,ll> Pll;

 typedef vector<int> VI;

 typedef vector<PII> VII;

 typedef pair<ll,ll>P;

 #define N  400000+10

 #define M  800000+10

 #define INF 4e9+10

 #define fi first

 #define se second

 #define MP make_pair

 #define pb push_back

 #define pi acos(-1)

 #define mem(a,b) memset(a,b,sizeof(a))

 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)

 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)

 #define lowbit(x) x&(-x)

 #define Rand (rand()*(1<<16)+rand())

 #define id(x) ((x)<=B?(x):m-n/(x)+1)

 #define ls p<<1

 #define rs p<<1|1

 #define fors(i) for(auto i:e[x]) if(i!=p)

 const int MOD=1e9+,inv2=(MOD+)/;

       //int p=1e6+3;

       //double eps=1e-6;

       int dx[]={-,,,};

       int dy[]={,,-,};

 struct edge

 {

     int x,y,l,a;

 }a[M];

 bool cmp(edge a,edge b)

 {

     return a.a>b.a;

 }

 ll dis[N],val[N];

 int f[N][],head[N],vet[M],nxt[M],len[M],vis[N],fa[N],n,m,num,tot;

 int read()

 {

    int v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 ll readll()

 {

    ll v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 void add(int a,int b,int c)

 {

     nxt[++tot]=head[a];

     vet[tot]=b;

     len[tot]=c;

     head[a]=tot;

 }

 void dijkstra()

 {

     priority_queue<Pli> q;

     rep(i,,n*) dis[i]=INF,vis[i]=;

     q.push(MP(,)); dis[]=;

     while(!q.empty())

     {

         int u=q.top().se;

         q.pop();

         if(vis[u]) continue;

         vis[u]=;

         int e=head[u];

         while(e)

         {

             int v=vet[e];

             if(dis[u]+len[e]<dis[v])

             {

                 dis[v]=dis[u]+len[e];

                 q.push(MP(-dis[v],v));

             }

             e=nxt[e];

         }

     }

 }

 int dsu(int k)

 {

     if(fa[k]!=k) fa[k]=dsu(fa[k]);

     return fa[k];

 }

 void Add(int x,int y)

 {

     f[y][]=x;

     dis[x]=min(dis[x],dis[y]);

 }

 int calc(int u,ll p)

 {

     per(i,,)

      if(val[f[u][i]]>p) u=f[u][i];

     return u;

 }

 void build()

 {

     num=n;

     rep(i,,*n) fa[i]=i;

     sort(a+,a+m+,cmp);

     rep(i,,m)

     {

         int p=dsu(a[i].x),q=dsu(a[i].y);

         if(p!=q)

         {

             num++;

             fa[p]=fa[q]=num;

             val[num]=a[i].a;

             Add(num,p);

             Add(num,q);

             if(num==*n-) break;

         }

     }

     rep(i,,)

      rep(j,,num) f[j][i]=f[f[j][i-]][i-];

 }

 void solve()

 {

     int q=read(),k=read(),s=read();

     ll lastans=;

     while(q--)

     {

         int v=read();

         ll p=readll();

         if(k==)

         {

             v=(v-)%n+;

             p=p%(s+);

         }

          else

          {

              v=(v+lastans-)%n+;

              p=(p+lastans)%(s+);

          }

         int t=calc(v,p);

         lastans=dis[t];

         printf("%lld\n",lastans);

     }

 }

 int main()

 {

     int cas=read();

     while(cas--)

     {

         n=read(),m=read();

         tot=;

         rep(i,,n) head[i]=;

         rep(i,,m)

         {

             a[i].x=read(),a[i].y=read(),a[i].l=read(),a[i].a=read();

             add(a[i].x,a[i].y,a[i].l);

             add(a[i].y,a[i].x,a[i].l);

         }

         dijkstra();

         build();

         solve();

     }

     return ;

 }