分析：
可以证明，任意两点间的符合题目要求的路径必然是在MST上的。
有了这个，这题就水了。。。我没有想到，是venique神犇告诉我的
然后在MST上做LCA倍增，顺便维护d[i][j]表示i到他的2^j倍祖先的最大权，就好了~
我是蒟蒻。。LCA写萎了。。看了venique的代码，才发现错。。。
View Code
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 #include <iostream> 6 7 #define N 110000 8 #define M 1000000 9 10 using namespace std; 11 12 struct KRU 13 { 14 int a,b,e,d; 15 }kru[M]; 16 17 int head[N],next[M],to[M],len[M],cnt,n,m,qu,f[N][22],d[N][22],fa[N],dpt[N],q[N]; 18 19 inline void add(int u,int v,int w) 20 { 21 to[cnt]=v; len[cnt]=w; next[cnt]=head[u]; head[u]=cnt++; 22 } 23 24 inline bool cmp(const KRU &a,const KRU &b) 25 { 26 return a.d<b.d; 27 } 28 29 void read() 30 { 31 memset(head,-1,sizeof head); cnt=0; 32 scanf("%d%d",&n,&m); 33 for(int i=1;i<=m;i++) scanf("%d%d%d",&kru[i].a,&kru[i].b,&kru[i].d); 34 } 35 36 int findfa(int x) 37 { 38 if(fa[x]!=x) fa[x]=findfa(fa[x]); 39 return fa[x]; 40 } 41 42 void kruskal() 43 { 44 sort(kru+1,kru+1+m,cmp); 45 for(int i=1;i<=n;i++) fa[i]=i; 46 int num=1; 47 for(int i=1;i<=m;i++) 48 if(findfa(kru[i].a)!=findfa(kru[i].b)) 49 { 50 fa[findfa(kru[i].a)]=findfa(kru[i].b); 51 num++; 52 add(kru[i].a,kru[i].b,kru[i].d); add(kru[i].b,kru[i].a,kru[i].d); 53 if(num==n) break; 54 } 55 } 56 57 void bfs() 58 { 59 int h=1,t=2,sta; 60 q[1]=1; dpt[1]=1; 61 while(h<t) 62 { 63 sta=q[h++]; 64 for(int i=head[sta];~i;i=next[i]) 65 if(to[i]!=f[sta][0]) 66 { 67 dpt[to[i]]=dpt[sta]+1; 68 f[to[i]][0]=sta; 69 d[to[i]][0]=len[i]; 70 q[t++]=to[i]; 71 } 72 } 73 } 74 75 void initlca() 76 { 77 for(int j=1;j<=20;j++) 78 for(int i=1;i<=n;i++) 79 { 80 d[i][j]=max(d[i][j-1],d[f[i][j-1]][j-1]); 81 f[i][j]=f[f[i][j-1]][j-1]; 82 } 83 } 84 85 int lca(int x,int y) 86 { 87 int rt=0; 88 if(dpt[x]<dpt[y]) swap(x,y); 89 for(int i=20;i>=0;i--) 90 if(dpt[f[x][i]]>=dpt[y]) 91 { 92 rt=max(rt,d[x][i]); 93 x=f[x][i]; 94 } 95 if(x==y) return rt; 96 for(int i=20;i>=0;i--) 97 if(f[x][i]!=f[y][i]) 98 { 99 rt=max(rt,max(d[x][i],d[y][i])); 100 x=f[x][i]; y=f[y][i]; 101 } 102 return max(rt,max(d[x][0],d[y][0])); 103 } 104 105 void go() 106 { 107 kruskal(); 108 bfs(); 109 initlca(); 110 scanf("%d",&qu); 111 int si=1,x,y,p1,p2,q1,q2; 112 for(int i=1;i<=qu;i++) 113 { 114 scanf("%d%d%d%d",&p1,&p2,&q1,&q2); 115 x=(long long)(si+p1)*p2%n+1; 116 y=(long long)(si+q1)*q2%n+1; 117 si=lca(x,y); 118 printf("%d\n",si); 119 } 120 } 121 122 int main() 123 { 124 read(); 125 go(); 126 return 0; 127 }