道路修建 Large
Time Limit: 5000ms
Memory Limit: 131072KB
64-bit integer IO format: %lld Java class name: Main Type: None Graph Theory 2-SAT Articulation/Bridge/Biconnected Component Cycles/Topological Sorting/Strongly Connected Component Shortest Path Bellman Ford Dijkstra/Floyd Warshall Euler Trail/Circuit Heavy-Light Decomposition Minimum Spanning Tree Stable Marriage Problem Trees Directed Minimum Spanning Tree Flow/Matching Graph Matching Bipartite Matching Hopcroft–Karp Bipartite Matching Weighted Bipartite Matching/Hungarian Algorithm Flow Max Flow/Min Cut Min Cost Max Flow DFS-like Backtracking with Pruning/Branch and Bound Basic Recursion IDA* Search Parsing/Grammar Breadth First Search/Depth First Search Advanced Search Techniques Binary Search/Bisection Ternary Search Geometry Basic Geometry Computational Geometry Convex Hull Pick's Theorem Game Theory Green Hackenbush/Colon Principle/Fusion Principle Nim Sprague-Grundy Number Matrix Gaussian Elimination Matrix Exponentiation Data Structures Basic Data Structures Binary Indexed Tree Binary Search Tree Hashing Orthogonal Range Search Range Minimum Query/Lowest Common Ancestor Segment Tree/Interval Tree Trie Tree Sorting Disjoint Set String Aho Corasick Knuth-Morris-Pratt Suffix Array/Suffix Tree Math Basic Math Big Integer Arithmetic Number Theory Chinese Remainder Theorem Extended Euclid Inclusion/Exclusion Modular Arithmetic Combinatorics Group Theory/Burnside's lemma Counting Probability/Expected Value Others Tricky Hardest Unusual Brute Force Implementation Constructive Algorithms Two Pointer Bitmask Beginner Discrete Logarithm/Shank's Baby-step Giant-step Algorithm Greedy Divide and Conquer Dynamic Programming Tag it!
无向图
初始有
个点，从
到依次标号，但是没有边，
接下来有
次操作，从到依次标号，你需要对每种操作输出相应的结果，操作分为两种：
| 输入格式 | 操作说明 | 输出结果 |
| 0_u_v | 加入一条连接标号为 | 输出加边后图 |
| 1_u_v | 查询标号为 | 如果连通，输出 |
，表示最早在第
。（输入格式中的下划线‘_’表示实际输入文件中的空格）
Input
第一行是一个正整数
，表示测试数据的组数，
对于每组测试数据，
第一行包含两个整数
、
，
接下来行，每行是
个整数
、
、
，请注意所给的、均是经过加密的，
解密方式是
、
，其中
表示上一次操作的输出结果，
初始
，保证
，解密后
且
。
Output
对于每组测试数据，
输出行，每行包含一个整数，表示操作的输出结果。
Sample Input
14 70 1 21 1 00 1 30 0 11 0 10 1 71 0 5
Sample Output
3022316
Source
#include#define REP(i,a,b) for(int i=a;i<=b;i++)#define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll;const int maxn=1000100;const int INF=1e9+10;int n,m;int fa[maxn],val[maxn];int rk[maxn];int op,u,v;int vis[maxn];int find(int x){ return fa[x]==x?x:find(fa[x]);}int main(){ freopen("in.txt","r",stdin); int T;cin>>T; while(T--){ scanf("%d%d",&n,&m); REP(i,1,n) fa[i]=i,val[i]=0; REP(i,1,n) rk[i]=1; REP(i,1,n) vis[i]=0; int lans=0,cnt=n; REP(i,1,m){ scanf("%d%d%d",&op,&u,&v); u^=lans;v^=lans; int x=find(u),y=find(v); if(op==0){ if(x!=y){ if(rk[x]>rk[y]) swap(x,y); fa[x]=y; rk[y]=max(rk[y],rk[x]+1); val[x]=i; cnt--; } lans=cnt; } else{ if(x!=y) lans=0; else{ int t=u; vis[x]=i; while(fa[t]!=t) vis[t]=i,t=fa[t]; int lca=x; t=v; while(fa[t]!=t){ if(vis[t]==i){ lca=t;break; } t=fa[t]; } lans=0; while(u!=lca) lans=max(lans,val[u]),u=fa[u]; while(v!=lca) lans=max(lans,val[v]),v=fa[v]; } } printf("%d\n",lans); } } return 0;}