\u96be\u5ea6&\u63a8\u8350\u6307\u6570\uff1a<\/p>\n
<\/p>\n
\u94fe\u63a5\uff1aCF<\/a> \/ luogu<\/a><\/p>\n Trees of Tranquillity<\/strong><\/p>\n<\/blockquote>\n \u5b81\u9759\u7684\u6811<\/strong><\/p>\n Soroush and Keshi each have a labeled and rooted tree on $n$ vertices. Both of their trees are rooted from vertex $ 1 $ .<\/p>\n<\/blockquote>\n Soroush \u548c Keshi \u90fd\u6709\u4e00\u4e2a\u505a\u4e86\u6807\u8bb0\u7684\u6709\u7740 $ n $ \u4e2a\u8282\u70b9\u7684\u6709\u6839\u6811\u3002\u8fd9\u4e24\u9897\u6811\u90fd\u4ee5\u8282\u70b9 $ 1 $ \u4e3a\u6839\u3002<\/p>\n Soroush and Keshi used to be at war. After endless decades of fighting, they finally became allies to prepare a Codeforces round. To celebrate this fortunate event, they decided to make a memorial graph on $ n $ vertices.<\/p>\n<\/blockquote>\n Soroush \u548c Keshi \u66fe\u7ecf\u8fdb\u884c\u8fc7\u6fc0\u70c8\u7684\u7ade\u4e89\u3002\u5728\u7ade\u4e89\u7684\u6700\u540e\u65f6\u671f\uff0c\u4ed6\u4eec\u6210\u4e3a\u4e86\u540c\u76df\u6765\u4e00\u8d77\u51c6\u5907 Codeforces \u6bd4\u8d5b\u3002\u4e3a\u4e86\u5e86\u795d\u8fd9\u4e2a\u5e78\u8fd0\u65f6\u523b\uff0c\u4ed6\u4eec\u51b3\u5b9a\u5236\u4f5c\u4e00\u4e2a\u6709 $ n $ \u4e2a\u8282\u70b9\u7684\u7eaa\u5ff5\u56fe\u3002<\/p>\n They add an edge between vertices $ u $ and $ v $ in the memorial graph if both<\/strong> of the following conditions hold:<\/p>\n \u5f53\u4e24\u4e2a\u70b9 $ u $ \u548c $ v $ \u6ee1\u8db3\u4ee5\u4e0b\u6761\u4ef6\u65f6\uff0c\u5b83\u4eec\u5728\u7eaa\u5ff5\u56fe\u4e0a\u9762\u6709\u4e00\u6761\u8fb9\u3002<\/p>\n Here vertex $ u $ is considered ancestor of vertex $ v $, if $ u $ lies on the path from $ 1 $ (the root) to the $ v $.<\/p>\n<\/blockquote>\n \u5982\u679c $ u $ \u662f $ v $ \u7684\u7956\u5148\uff0c\u5219 $ u $ \u5728 $ v $ \u5230\u6839\u8282\u70b9\u7684\u6700\u77ed\u8def\u5f84\u4e0a\u3002<\/p>\n Popping out of nowhere, Mashtali tried to find the maximum clique in the memorial graph for no reason. He failed because the graph was too big.<\/p>\n<\/blockquote>\n \u4e0d\u77e5\u4ece\u54ea\u91cc\u5192\u51fa\u6765\u7684 Mashtali \u60f3\u8981\u5728\u8fd9\u4e2a\u7eaa\u5ff5\u56fe\u4e2d\u627e\u5230\u6700\u5927\u7684\u6d3e\u7cfb\u3002<\/p>\n Help Mashtali by finding the size of the maximum clique in the memorial graph.<\/p>\n<\/blockquote>\n \u5e2e\u52a9 Mashtali \u627e\u5230\u8fd9\u4e2a\u6700\u5927\u6d3e\u7cfb\u7684\u8282\u70b9\u6570\u5427\uff01<\/p>\n As a reminder, clique is a subset of vertices of the graph, each two of which are connected by an edge.<\/p>\n<\/blockquote>\n \u63d0\u793a\uff1a\u6d3e\u7cfb\u662f\u4e00\u4e2a\u56fe\u7684\u5b50\u96c6\uff0c\u5728\u6d3e\u7cfb\u4e2d\uff0c\u4efb\u610f\u4e24\u70b9\u4e4b\u95f4\u90fd\u6709\u4e00\u6761\u8fb9\u3002<\/p>\n \u7b97\u6cd5\uff1adfs<\/p>\n \u6570\u636e\u7ed3\u6784\uff1a\u5e73\u8861\u6811\uff08\u53ef\u7528 \u4e0b\u6587\u4e2d Soroush \u7684\u6811\u7b80\u79f0 st \uff0cKeshi \u7684\u6811\u7b80\u79f0 kt \u3002<\/p>\n \u4e0d\u96be\u53d1\u73b0\uff0c\u5728\u9898\u76ee\u8981\u6c42\u7684\u6d3e\u7cfb\u4e2d\u7684\u4efb\u610f\u4e24\u70b9 $ u,v $ \uff0c\u603b\u6ee1\u8db3\u5728 st \u4e2d\u4e00\u8005\u662f\u53e6\u4e00\u8005\u7684\u7956\u5148\uff0c\u4e14\u5728kt\u4e2d\u6ca1\u6709\u7956\u5148\u5173\u7cfb\u3002<\/p>\n \u540c\u65f6\u4e0d\u96be\u53d1\u73b0\uff0c\u8fd9\u4e2a\u6d3e\u7cfb\u4e2d\u7684\u70b9\uff0c\u5fc5\u7136\u662f st \u7684\u4e00\u6761\u4ece\u6839\u5230\u53f6\u5b50\u7684\u6811\u94fe\u7684\u5b50\u96c6\u3002<\/p>\n \u90a3\u4e48\u6211\u4eec\u53ef\u4ee5\u5148\u5ffd\u7565\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u679a\u4e3e st \u7684\u6bcf\u4e00\u6761\u4ece\u6839\u5230\u53f6\u5b50\u7684\u6811\u94fe\u770b\u770b\u6709\u6ca1\u6709\u529e\u6cd5\u6765\u627e\u5230\u9898\u76ee\u8981\u6c42\u7684\u6d3e\u7cfb\u3002\u6211\u4eec\u5148\u5047\u8bbe\u8fd9\u4e2a\u6811\u94fe\u4e0a\u6240\u6709\u7684\u70b9\u90fd\u5728\u6d3e\u7cfb\u4e2d\uff0c\u7136\u540e\u518d\u60f3\u529e\u6cd5\u5220\u9664\u4e00\u4e9b\u70b9\u3002\u53ef\u4ee5\u53d1\u73b0\uff0c\u5982\u679c\u5b58\u5728\u4e00\u4e2a\u70b9 $ u $ \u5728 kt \u4e2d\u662f $ v $ \u7684\u7956\u5148\uff08$ u,v $ \u5747\u662f\u88ab\u9009\u5b9a\u7684\u6811\u94fe\u4e2d\u7684\u8282\u70b9\uff09\uff0c\u90a3\u4e48\u5220\u9664 $ u $ \u603b\u662f\u6bd4\u5220\u9664 $ v $ \u8981\u4f18\u3002\u56e0\u4e3a\u5982\u679c\u8981\u5220\u9664 $ v $ \u6709\u53ef\u80fd\u8fd8\u8981\u5220\u9664\u5176\u4ed6\u4ee5 $ u $ \u4e3a\u7956\u5148\u7684\u8282\u70b9\uff0c\u800c\u5220\u9664 $ u $ \u5c31\u4e0d\u7528\u5220\u9664\u4ee5\u5b83\u4e3a\u7956\u5148\u7684\u5176\u5b83\u8282\u70b9\u3002\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u53d1\u73b0\uff0c\u5bf9\u4e8e\u9009\u5b9a\u7684\u4e00\u6761\u6811\u94fe\uff0c\u6211\u4eec\u53ea\u9700\u8981\u5220\u9664\u6240\u6709\u5728 kt \u4e2d\u4e3a\u5176\u5b83\u8282\u70b9\u7956\u5148\u7684\u70b9\u5373\u53ef\u3002<\/p>\n \u5982\u4f55\u5224\u65ad\u4e00\u4e2a\u8282\u70b9\u662f\u5426\u662f\u53e6\u4e00\u4e2a\u8282\u70b9\u7684\u7956\u5148\u5462\uff1f \u53ef\u4ee5\u8003\u8651\u4f7f\u7528 dfs \u5e8f\u3002\u6211\u4eec\u4ee5 in[i] \u4ee3\u8868 $i$ \u8282\u70b9\u5728\u521a\u8fdb\u5165 dfs \u65f6\u7684 dfs \u5e8f\uff0c\u4ee5 out[i] \u4ee3\u8868 $i$ \u8282\u70b9\u5728\u51fa dfs \u65f6\u7684 dfs \u5e8f\u3002<\/p>\n \u90a3\u4e48\u5982\u679c $ u $ \u4e3a $ v $ \u7684\u7956\u5148\uff0c\u5f53\u4e14\u4ec5\u5f53 in[u]<in[v] && out[u]>=out[v] .<\/p>\n \u63a5\u4e0b\u6765\u8003\u8651\u679a\u4e3e st \u4e0a\u5355\u4e00\u6811\u94fe\u662f\u5982\u4f55\u5904\u7406\u6811\u94fe\u4e0a\u7684\u70b9\u3002\u6211\u4eec\u53ef\u4ee5\u4ece\u6839\u8282\u70b9\u6328\u4e2a\u628a\u6811\u94fe\u4e0a\u7684\u70b9\u52a0\u5165\u6d3e\u7cfb\u96c6\u5408\uff0c\u5f53\u6dfb\u52a0 $ i $ \u8282\u70b9\u65f6\uff0c\u5982\u679c\u5b58\u5728 $ i $ \u8282\u70b9\u7684\u7956\u5148\uff0c\u5219\u5220\u9664\u5176\u7956\u5148\u5e76\u52a0\u5165 $ i $ \u8282\u70b9\uff1b\u5982\u679c $ i $ \u8282\u70b9\u662f\u5df2\u6dfb\u52a0\u7684\u522b\u7684\u8282\u70b9\u7684\u7956\u5148\uff0c\u5219\u4e0d\u6dfb\u52a0 $ i $ \u8282\u70b9\uff1b\u5982\u679c\u4e0a\u9762\u4e24\u70b9\u90fd\u4e0d\u6ee1\u8db3\uff0c\u5219\u76f4\u63a5\u6dfb\u52a0 $ i $ \u8282\u70b9\u3002\u6700\u540e\u770b\u770b\u80fd\u6dfb\u52a0\u591a\u5c11\u4e2a\u8282\u70b9\u5c31\u662f\u8fd9\u4e2a\u6811\u94fe\u7684\u7b54\u6848\u3002<\/p>\n \u5728\u6dfb\u52a0 $ i $ \u8282\u70b9\u65f6\uff0c\u6d3e\u7cfb\u96c6\u5408\u4e2d\u6700\u591a\u53ea\u80fd\u5b58\u5728\u4e00\u4e2a $ i $ \u8282\u70b9\u7684\u7956\u5148\u3002\u5982\u679c\u8fd9\u4e2a\u7956\u5148\u5b58\u5728\uff0c\u6211\u4eec\u8bbe\u5b83\u4e3a $ u $ \uff0c\u5219 in[u] \u5728\u96c6\u5408\u4e2d\u662f in[i] \u7684\u524d\u9a71\u3002\u867d\u7136\u8bf4\u6d3e\u7cfb\u96c6\u5408\u4e2d\u53ef\u80fd\u5b58\u5728\u591a\u4e2a\u4ee5 $ i $ \u4e3a\u7956\u5148\u7684\u8282\u70b9\uff0c\u4f46\u662f\u5982\u679c\u5b58\u5728\uff0c\u5219 in[i] \u5728\u96c6\u5408\u4e2d\u7684\u540e\u7ee7\u4e00\u5b9a\u662f\u4ee5 $ i $ \u4e3a\u7956\u5148\u7684\u8282\u70b9\u3002\u90a3\u4e48\u7528\u4e00\u68f5\u5e73\u8861\u6811\u7ef4\u62a4\u5373\u53ef\u3002<\/p>\n \u600e\u4e48\u628a\u94fe\u7684\u60c5\u51b5\u6269\u5c55\u5230\u6811\u5462\uff1f\u6211\u4eec\u53ef\u4ee5\u5229\u7528\u56de\u6eaf\u7b97\u6cd5\uff0c\u6bcf\u4e2a\u8282\u70b9\u904d\u5386\u7ed3\u675f\u540e\u5c06\u5176\u5bf9\u96c6\u5408\u7684\u4fee\u6539\u201c\u64a4\u9500\u201d\uff0c\u5c31\u53ef\u4ee5\u5b9e\u73b0\u6269\u5c55\u7684\u5230\u6811\u7684\u60c5\u51b5\u3002<\/p>\n \u65f6\u95f4\u590d\u6742\u5ea6\uff1a$ O(n\\log n) $<\/p>\n \u4ee3\u7801\uff08\u4f7f\u7528\u975e\u65cb\u5f0fTreap\u5b9e\u73b0\uff09\uff1a<\/p>\n \u96be\u5ea6&\u63a8\u8350\u6307\u6570\uff1a \u601d\u7ef4\u96be\u5ea6\uff1a\u63d0\u9ad8+\/\u7701\u9009- \u5b9e\u73b0\u96be\u5ea6\uff1a\u63d0\u9ad8+\/\u7701\u9009- \u63a8\u8350\u6307\u6570\uff1a8.0\uff08\u63a8\u8350\u6307\u6570\u6700\u9ad8\u4e3a […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[10],"class_list":["post-67","post","type-post","status-publish","format-standard","hentry","category-4","tag-10"],"_links":{"self":[{"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/posts\/67","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/qwq.cafe\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=67"}],"version-history":[{"count":2,"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/posts\/67\/revisions"}],"predecessor-version":[{"id":69,"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/posts\/67\/revisions\/69"}],"wp:attachment":[{"href":"https:\/\/qwq.cafe\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=67"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/qwq.cafe\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=67"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/qwq.cafe\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=67"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\u9898\u76ee\u7ffb\u8bd1<\/h2>\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\u9898\u89e3<\/h2>\n
std::set<\/code> \u4ee3\u66ff\uff09<\/p>\nvoid dfs(int i)\n{\n in[i]=++dfn;\n dfni[dfn]=i;\n for(int p=V[i].eh;p;p=E[p].next)\n {\n dfs_kt(E[p].to);\n }\n out[i]=dfn;\n}<\/code><\/pre>\n#pragma GCC optimize ("O2")\n\n#include<stdio.h>\n#include<stdlib.h>\n#include<time.h>\n#include<string.h>\n#define MAXN 300005\n#define lc nodes[i].ch[0]\n#define rc nodes[i].ch[1]\n\nstruct treap{\n struct node{\n int v;\n int rnd;\n int ch[2];\n int siz;\n }nodes[MAXN*2];\n int tot=0,root=0;\n\n void init()\n {\n tot=0;\n root=0;\n }\n\n void pushup(int i)\n {\n nodes[i].siz=nodes[lc].siz+nodes[rc].siz+1;\n }\n\n int new_node(int v)\n {\n int i=++tot;\n nodes[i].v=v;\n nodes[i].rnd=rand();\n nodes[i].siz=1;\n lc=rc=0;\n return i;\n }\n\n void split(int i,int v,int& x,int& y)\n {\n if(!i) x=y=0;\n else\n {\n if(nodes[i].v<=v) split(rc,v,rc,y),x=i;\n else split(lc,v,x,lc),y=i;\n pushup(i);\n }\n }\n\n int merge(int x,int y)\n {\n if(!x||!y) return x+y;\n int i;\n if(nodes[x].rnd>nodes[y].rnd)\n {\n i=x;\n rc=merge(rc,y);\n }\n else\n {\n i=y;\n lc=merge(x,lc);\n }\n pushup(i);\n return i;\n }\n\n void insert(int v)\n {\n int x,y;\n split(root,v,x,y);\n root=merge(merge(x,new_node(v)),y);\n }\n\n void remove(int v)\n {\n int i,x,y;\n split(root,v,x,y);\n split(x,v-1,x,i);\n i=merge(lc,rc);\n root=merge(merge(x,i),y);\n }\n\n int find_pre(int v)\n {\n int x,y,i,ans;\n split(root,v-1,x,y);\n i=x;\n while(rc) i=rc;\n ans=nodes[i].v;\n root=merge(x,y);\n return ans;\n }\n\n int find_next(int v)\n {\n int x,y,i,ans;\n split(root,v,x,y);\n i=y;\n while(lc) i=lc;\n ans=nodes[i].v;\n root=merge(x,y);\n return ans;\n }\n\n int size()\n {\n return nodes[root].siz;\n }\n}t;\n\nstruct tree{\n struct node{\n int eh;\n }V[MAXN];\n\n struct edge{\n int to;\n int next;\n }E[MAXN];\n\n int tot;\n\n void add_edge(int from,int to)\n {\n E[++tot]=(edge){to,V[from].eh};\n V[from].eh=tot;\n }\n\n void init(int n)\n {\n tot=0;\n memset(V+1,0,sizeof(node)*n);\n \/\/\u6ce8\u610f\u8fd9\u91cc\u4e0d\u80fd\u521d\u59cb\u5316\u6574\u4e2a\u6570\u7ec4\uff0c\u4e0d\u7136\u4f1a\u8d85\u65f6\n }\n}st,kt;\n\nint in[MAXN],out[MAXN];\nint dfn;\nint dfni[MAXN];\n\nvoid dfs_kt(int i)\n{\n auto& E=kt.E;\n auto& V=kt.V;\n in[i]=++dfn;\n dfni[dfn]=i;\n for(int p=V[i].eh;p;p=E[p].next)\n {\n dfs_kt(E[p].to);\n }\n out[i]=dfn;\n}\n\nint ans;\n\nvoid dfs_st(int i)\n{\n auto& E=st.E;\n auto& V=st.V;\n\n int j=dfni[t.find_next(in[i])],tmp=0;\n bool flag=false;\n\n if(!(j&&out[i]>=out[j]))\n {\n flag=true;\n t.insert(in[i]);\n j=dfni[t.find_pre(in[i])];\n if(j&&out[j]>=out[i])\n {\n tmp=in[j];\n t.remove(in[j]);\n }\n }\n\n if(t.size()>ans) ans=t.size();\n\n for(int p=V[i].eh;p;p=E[p].next)\n {\n dfs_st(E[p].to);\n }\n\n if(flag) t.remove(in[i]);\n if(tmp) t.insert(tmp);\n}\n\nint main()\n{\n srand((unsigned)time(NULL));\n int T,n,i,tmp;\n scanf("%d",&T);\n while(T--)\n {\n \/\/initialize\n scanf("%d",&n);\n st.init(n);\n kt.init(n);\n t.init();\n dfn=0;\n ans=0;\n\n \/\/input\n for(i=2;i<=n;i++)\n {\n scanf("%d",&tmp);\n st.add_edge(tmp,i);\n }\n for(i=2;i<=n;i++)\n {\n scanf("%d",&tmp);\n kt.add_edge(tmp,i);\n }\n\n \/\/solve\n dfs_kt(1);\n dfs_st(1);\n\n \/\/output\n printf("%d\\n",ans);\n }\n return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"