… \u7ed9\u5b9a\u4e00\u68f5 N \u4e2a\u7ed3\u70b9\u7684\u6709\u6839\u6811\u68ee\u6797\uff0c\u8fb9\u4e0a\u6709\u4e00\u4e2a\u989c\u8272\uff0c\u9700\u8981\u652f\u6301\u4e0b\u9762\u8fd9 3 \u4e2a\u64cd\u4f5c\u3002<\/p>\n
(.. N = 50, 000 ..)<\/p>\n
<\/p>\n
.. LRJ Preset 3 ..( \u4ecb\u4e8e UVa \u7ecf\u5e38\u65e0\u9650\u91cd\u5b9a\u5411\u3002\u3002\u53ef\u4ee5\u7528 Virtual Judge \u505a VPN .. .)<\/p>\n
… \u663e\u7136\u8fd9\u4e2a\u9898\u5bf9\u6211\u6765\u8bf4\u5df2\u7ecf\u53d8\u6210\u53ef\u505a\u9898\u4e86\u3002\u3002\u867d\u7136\u5f53\u65f6\u5c31\u53ea\u6709\u8df3\u8fc7\u7684\u4efd\u4e86\u3002\u3002
\n\uff08\u3002\u3002\u3002LCA \u7684\u5730\u65b9 WA \u4e86\u4e00\u6b21\u3002\u3002\u8fd8\u6709 mask \u7684\u5730\u65b9 WA \u4e86\u51e0\u6b21\u3002\u3002\u3002\uff09<\/p>\n
\r\n\/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **\/\r\n\r\n#include <algorithm>\r\n#include <iostream>\r\n#include <iomanip>\r\n#include <sstream>\r\n#include <cstring>\r\n#include <cstdio>\r\n#include <string>\r\n#include <vector>\r\n#include <bitset>\r\n#include <queue>\r\n#include <cmath>\r\n#include <ctime>\r\n#include <list>\r\n#include <set>\r\n#include <map>\r\n\r\nusing namespace std;\r\n\r\n#define REP(i, n) for (int i=0;i<int(n);++i)\r\n#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)\r\n#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)\r\n#define REP_1(i, n) for (int i=1;i<=int(n);++i)\r\n#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)\r\n#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)\r\n#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)\r\n#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)\r\n#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)\r\n#define REP_N(i, n) for (i=0;i<int(n);++i)\r\n#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)\r\n#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)\r\n#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)\r\n#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)\r\n#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)\r\n#define REP_1_N(i, n) for (i=1;i<=int(n);++i)\r\n#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)\r\n#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)\r\n#define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i)\r\n#define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i)\r\n#define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i)\r\n#define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i)\r\n#define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i)\r\n#define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i)\r\n\r\n#define DO(n) while(n--)\r\n#define DO_C(n) int n____ = n; while(n____--)\r\n#define TO(i, a, b) int s_=a<b?1:-1,b_=b+s_;for(int i=a;i!=b_;i+=s_)\r\n#define TO_1(i, a, b) int s_=a<b?1:-1,b_=b;for(int i=a;i!=b_;i+=s_)\r\n#define SQZ(i, j, a, b) for (int i=int(a),j=int(b)-1;i<j;++i,--j)\r\n#define SQZ_1(i, j, a, b) for (int i=int(a),j=int(b);i<=j;++i,--j)\r\n#define REP_2(i, j, n, m) REP(i, n) REP(j, m)\r\n#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)\r\n\r\n#define ALL(A) A.begin(), A.end()\r\n#define LLA(A) A.rbegin(), A.rend()\r\n#define CPY(A, B) memcpy(A, B, sizeof(A))\r\n#define INS(A, P, B) A.insert(A.begin() + P, B)\r\n#define ERS(A, P) A.erase(A.begin() + P)\r\n#define BSC(A, X) find(ALL(A), X) \/\/ != A.end()\r\n#define CTN(T, x) (T.find(x) != T.end())\r\n#define SZ(A) int(A.size())\r\n#define PB push_back\r\n#define MP(A, B) make_pair(A, B)\r\n\r\n#define Rush int T____; RD(T____); DO(T____)\r\n#pragma comment(linker, "\/STACK:36777216")\r\n#pragma GCC optimize ("O2")\r\n#define Ruby system("ruby main.rb")\r\n#define Haskell system("runghc main.hs")\r\n#define Pascal system("fpc main.pas")\r\n\r\n\/** I\/O Accelerator **\/\r\n\r\n\/* ... :" We are I\/O Accelerator ... Use us at your own risk ;) ... " .. *\/\r\n\r\ntemplate<class T> inline void RD(T &);\r\ntemplate<class T> inline void OT(const T &);\r\n\r\ninline int RD(){ int x; RD(x); return x;}\r\ntemplate<class T> inline T& _RD(T &x){ RD(x); return x;}\r\n\r\ntemplate<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}\r\ntemplate<class T0, class T1, class T2> inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);}\r\ntemplate<class T0, class T1, class T2, class T3> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3);}\r\ntemplate<class T0, class T1, class T2, class T3, class T4> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);}\r\ntemplate<class T0, class T1, class T2, class T3, class T4, class T5> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);}\r\ntemplate<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);}\r\ntemplate<class T0, class T1> inline void OT(T0 &x0, T1 &x1){OT(x0), OT(x1);}\r\ntemplate<class T0, class T1, class T2> inline void OT(T0 &x0, T1 &x1, T2 &x2){OT(x0), OT(x1), OT(x2);}\r\ntemplate<class T0, class T1, class T2, class T3> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);}\r\ntemplate<class T0, class T1, class T2, class T3, class T4> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}\r\ntemplate<class T0, class T1, class T2, class T3, class T4, class T5> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}\r\ntemplate<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}\r\n\r\ntemplate<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}\r\ntemplate<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}\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 T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}\r\ntemplate<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}\r\ntemplate<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}\r\ntemplate<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}\r\n\r\n\r\n\/** Add - On **\/\r\n\r\n\/\/ <<= ` 0. Daily Use .,\r\n\r\ntemplate<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;}\r\ntemplate<class T> inline void checkMax(T &a,const T b){if (b>a) a=b;}\r\ntemplate <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;}\r\ntemplate <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;}\r\ntemplate<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}\r\ntemplate<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}\r\ntemplate<class T> inline T sqr(T a){return a*a;}\r\ntemplate<class T> inline T cub(T a){return a*a*a;}\r\nint Ceil(int x, int y){return (x - 1) \/ y + 1;}\r\n\r\n\/\/ <<= ` 1. Bitwise Operation .,\r\n\r\ninline bool _1(int x, int i){return x & 1<<i;}\r\ninline int _1(int i){return 1<<i;}\r\ninline int _U(int i){return _1(i) - 1;};\r\n\r\ninline int count_bits(int x){\r\n x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);\r\n x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);\r\n x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);\r\n x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);\r\n x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);\r\n return x;\r\n}\r\n\r\ntemplate<class T> inline T low_bit(T x) {\r\n return x & -x;\r\n}\r\n\r\ntemplate<class T> inline T high_bit(T x) {\r\n T p = low_bit(x);\r\n while (p != x) x -= p, p = low_bit(x);\r\n return p;\r\n}\r\n\r\n\/\/ <<= ' 0. I\/O Accelerator interface .,\r\n\r\ntemplate<class T> inline void RD(T &x){\r\n \/\/cin >> x;\r\n \/\/scanf("%d", &x);\r\n 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\n \/\/char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';\r\n\r\n}\r\n\r\ninline void OT(int a, int b){\r\n printf("%d %d\\n", a, b);\r\n}\r\n\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 50009;\r\n\r\nint l[N], r[N], p[N], sz[N], color[N], delay[N], mask[N]; bool rt[N];\r\nint n, m;\r\n\r\n#define lx l[x]\r\n#define rx r[x]\r\n\r\ninline void Paint(int x, int c){\r\n if (x == 0) return;\r\n color[x] = delay[x] = mask[x] = c;\r\n}\r\n\r\ninline void Release(int x){\r\n if (x == 0 || !delay[x]) return;\r\n Paint(lx, delay[x]), Paint(rx, delay[x]);\r\n delay[x] = 0;\r\n}\r\n\r\ninline void Update(int x){\r\n sz[x] = sz[lx] + sz[rx] + 1;\r\n mask[x] = color[x] | mask[lx] | mask[rx];\r\n}\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]) Release(z), Set(y == l[z] ? l : r, z, x);\r\n else p[x] = z;\r\n\r\n Release(y), Release(x);\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 Update(y);\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), Release(x);\r\n rt[rx] = true, rt[rx = y] = false; Update(x);\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 Depth(int x){\r\n return sz[Access(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), Release(x); if (!p[x]) lca = x;\r\n rt[rx] = true, rt[rx = y] = false, Update(x);\r\n x = p[y = x];\r\n } while (x);\r\n return lca;\r\n}\r\n\r\n\r\n\/\/ Public :\r\n\r\nvoid Query(int x, int y){\r\n\r\n if (x == y || Root(x) != Root(y)){\r\n OT(0, 0);\r\n return;\r\n }\r\n\r\n Access(y); y = 0; do{\r\n Splay(x), Release(x); if (!p[x]) OT(sz[rx] + sz[y], count_bits(mask[rx] | mask[y]));\r\n rt[rx] = true, rt[rx = y] = false, Update(x);\r\n x = p[y = x];\r\n } while (x);\r\n}\r\n\r\nvoid Paint(int x, int y, int c){\r\n\r\n if (Root(x) != Root(y)) return;\r\n\r\n c = _1(c - 1), Access(y); y = 0; do{\r\n Splay(x), Release(x); if (!p[x]) Paint(rx, c), Paint(y, c);\r\n rt[rx] = true, rt[rx = y] = false, Update(x);\r\n x = p[y = x];\r\n } while (x);\r\n}\r\n\r\nvoid Link(int x, int y, int c){\r\n\r\n if (x == y || Root(x) == Root(y) && Lca(x, y) == x) return;\r\n\r\n c = _1(c - 1), Access(x), Splay(x), rt[lx] = true;\r\n lx = p[lx] = 0, p[x] = y, Paint(x, c), Update(x);\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 while (scanf("%d %d", &n, &m) != EOF){\r\n\r\n \/\/ Initializing Phase ...\r\n\r\n REP_1(i, n) sz[i] = 1, rt[i] = true, RD(p[i]);\r\n\r\n REP_1(i, n) color[i] = mask[i] = _1(RD() - 1);\r\n\r\n \/\/ Interaction Phase ...\r\n\r\n int op, a, b, c;\r\n\r\n DO(m){\r\n RD(op); if (op == 3) RD(a, b), Query(a, b);\r\n else if (op == 2) RD(a, b, c), Paint(a, b, c);\r\n else RD(a, b, c), Link(a, b, c);\r\n }\r\n\r\n \/\/ Rececling ....\r\n\r\n RST(p, l, r, delay);\r\n }\r\n}\r\n<\/pre>\nExternal link :<\/h3>\n
http:\/\/acm.hust.edu.cn:8080\/judge\/problem\/viewProblem.action?id=18699<\/a>
\nhttp:\/\/blog.renren.com\/blog\/247466695\/722043176<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"Brief description : … \u7ed9\u5b9a\u4e00\u68f5 N \u4e2a\u7ed3\u70b9\u7684\u6709\u6839\u6811\u68ee\u6797\uff0c\u8fb9\u4e0a\u6709\u4e00\u4e2a\u989c\u8272\uff0c\u9700\u8981\u652f\u6301\u4e0b\u9762\u8fd9 3 \u4e2a\u64cd\u4f5c\u3002 Query(x, y) \u5982\u679c x \u548c y \u5728\u540c\u4e00\u68f5\u5b50\u6811\u4e2d\uff0c\u5219\u8be2\u95ee\u8def\u5f84\u4e0a\u8fb9\u7684\u6570\u76ee\u3001\u548c\u989c\u8272\u7684\u79cd\u7c7b\u6570\u3002 Paint(x, y, c) \u5982\u679c x \u548c y \u5728\u540c\u4e00\u68f5\u5b50\u6811\u4e2d\uff0c\u5219\u5c06\u7ecf\u8fc7\u7684\u8def\u5f84\u4e0a\u6240\u6709\u8fb9\u67d3\u8272\u4e3a c\u3002 Link(x, y, c) \u5982\u679c x \u548c y \u5728\u540c\u4e00\u4e2a\u5b50\u6811\u4e2d\uff0c\u4e14 x \u4e0d\u4e3a y \u7684\u7956\u5148\uff0c\u90a3\u4e48\u5207\u65ad x \u540c\u5176\u7236\u4eb2\u7684\u8054\u7cfb\uff0c\u4e4b\u540e\u7528\u4e00\u6761\u989c\u8272\u4e3a c \u7684\u8fb9\u8fde\u63a5 x\u3001y\u3002 (.. N = 50, 000 ..)<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[31],"tags":[],"class_list":["post-40","post","type-post","status-publish","format-standard","hentry","category-uva"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-E","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/40","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=40"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/40\/revisions"}],"predecessor-version":[{"id":41,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/40\/revisions\/41"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=40"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=40"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=40"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}