… \u7565. .<\/p>\n
<\/p>\n
… \u7565 ..<\/p>\n
\r\n\/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **\/\r\n#include <iostream>\r\n#include <cstring>\r\n#include <cstdio>\r\nusing namespace std;\r\n#define REP_1(i, n) for (int i=1;i<=int(n);++i)\r\n#define DO_C(n) int n____ = n; while(n____--)\r\ntemplate<class T> inline void RD(T &x){char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';}\r\ninline int RD(){ int x; RD(x); return x;}\r\ninline void RS(char *s){scanf("%s", s);}\r\ntemplate<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}\r\ntemplate<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);}\r\ntemplate<class T> inline void OT(const T &x){printf("%d\\n", x);}\r\n\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 50009;\r\n\r\nint l[N], r[N], p[N]; bool rt[N];\r\nint n;\r\n\r\n#define lx l[x]\r\n#define rx r[x]\r\n\r\ninline void Set(int l[], int y, int x){\r\n l[y] = x, p[x] = y;\r\n}\r\n\r\ninline void Rotate(int x){\r\n int y = p[x], z = p[y];\r\n\r\n if (!rt[y]) Set(y == l[z] ? l : r, z, x);\r\n else p[x] = z;\r\n\r\n if (x == l[y]) Set(l, y, rx), Set(r, x, y);\r\n else Set(r, y, lx), Set(l, x, y);\r\n\r\n if (rt[y]) rt[y] = false, rt[x] = true;\r\n}\r\n\r\ninline void Splay(int x){\r\n while (!rt[x]) Rotate(x);\r\n}\r\n\r\nint Access(int x){\r\n int y = 0; do{\r\n Splay(x);\r\n rt[rx] = true, rt[rx = y] = false;\r\n x = p[y = x];\r\n } while (x);\r\n return y;\r\n}\r\n\r\ninline int Root(int x){\r\n for (x = Access(x); lx ; x = lx);\r\n return x;\r\n}\r\n\r\ninline int Lca(int x, int y){\r\n int lca; Access(y); y = 0; do{\r\n Splay(x); if (!p[x]) lca = x;\r\n rt[rx] = true, rt[rx = y] = false;\r\n x = p[y = x];\r\n } while (x);\r\n return lca;\r\n}\r\n\r\n\/\/ Public :\r\n\r\nvoid Link(int y, int x){\r\n\r\n if (y && (x == y || Root(x) == Root(y) && Lca(x, y) == x)) return;\r\n\r\n Access(x), Splay(x), rt[lx] = true;\r\n lx = p[lx] = 0, p[x] = y;\r\n Access(x);\r\n}\r\n\r\nint main(){\r\n\r\n \/\/freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n\r\n bool first_blood = true;\r\n\r\n while (scanf("%d", &n) != EOF){\r\n\r\n \/\/ Initializing Phase ...\r\n\r\n if (first_blood) first_blood = false; else puts("");\r\n\r\n REP_1(i, n) rt[i] = true, RD(p[i]);\r\n\r\n \/\/ Interaction Phase ...\r\n\r\n char cmd[9]; DO_C(RD()){\r\n RS(cmd); if (cmd[0] == 'Q') OT(Root(RD()));\r\n else Link(RD(), RD());\r\n }\r\n\r\n \/\/ Rececling ....\r\n\r\n RST(p, l, r);\r\n }\r\n}\r\n\r\n<\/pre>\nExternal link :<\/h3>\n