\u6211\u4eec\u5c1d\u8bd5\u7c7b\u6bd4\u5e8f\u5217\u4e0a\u7684\u60c5\u51b5\u6765\u770b\u8fd9\u4e00\u9898\u3002 <\/p>\n\n\n\n
\u5bf9\u4e8e\u5e8f\u5217\u4e0a\u7684\u60c5\u51b5\uff0c\u6211\u4eec\u7ef4\u62a4\u4e00\u4e2a\u96c6\u5408 \\(S\\) \uff0c\u5176\u4e2d \\(S_i\\) \u8868\u793a\uff0c\u957f\u5ea6\u4e3a \\(i\\) \u7684\u6700\u957f\u4e0d\u4e0b\u964d\u5b50\u5e8f\u5217\u7684\u6700\u540e\u4e00\u9879\u7684\u6700\u5c0f\u503c\u3002 \u90a3\u4e48\uff0c\u5bf9\u4e8e\u65b0\u7684\u70b9\uff0c\u6211\u4eec\u8003\u8651\u4e24\u79cd\u60c5\u51b5\uff1a\u5b83\u80fd\u52a0\u957f\u5e8f\u5217\uff0c\u90a3\u4e48\u5c31\u52a0\u957f\uff1b\u5426\u5219\uff0c\u5c31\u5c3d\u53ef\u80fd\u5730\u66f4\u65b0\u6700\u5c0f\u503c\u3002 <\/p>\n\n\n\n
\u5bf9\u4e8e\u6811\u4e0a\u7684\u60c5\u51b5\uff0c\u6211\u4eec\u9996\u5148\u5c1d\u8bd5\u8003\u8651\u4e00\u79cd \\(O(n^2logn)\\) \u7684\u505a\u6cd5\u3002\u6211\u4eec\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u8282\u70b9\u7ef4\u62a4\u4e00\u4e2a\u96c6\u5408 \\(S_i\\)\uff0c \u5176\u4e2d \\(S_{i,j}\\) \u8868\u793a\u4ec5\u7528\u5230\u8fd9\u4e2a\u8282\u70b9\u53ca\u5176\u5b50\u6811\u5185\u7684\u6240\u6709\u70b9\uff0c\u80fd\u591f\u6784\u9020\u7684\u5927\u5c0f\u4e3a \\(j\\) \u7684\u96c6\u5408\u7684\u6700\u5c0f\u9879\u7684\u6700\u5927\u503c\u3002 <\/p>\n\n\n\n
\u5982\u679c\u6211\u4eec\u628a\u6240\u6709\u5b50\u8282\u70b9\u7684 \\(S\\) \u90fd\u5df2\u7ecf\u6574\u5408\u5728\u4e00\u8d77\u4e86\uff0c\u90a3\u4e48\u66f4\u65b0\u6839\u8282\u70b9\u662f\u6bd4\u8f83\u5bb9\u6613\u7684\uff1a\u7c7b\u6bd4\u4e8e\u5e8f\u5217\u5373\u53ef\u3002 \u95ee\u9898\u5728\u4e8e\u5b50\u8282\u70b9\u8981\u5982\u4f55\u5408\u5e76\u3002 <\/p>\n\n\n\n
\u4ed4\u7ec6\u89c2\u5bdf\uff0c\u53d1\u73b0\uff0c\u5b50\u8282\u70b9\u7684\u5408\u5e76\u662f\u4e00\u4e2a\u7c7b\u4f3c\u4e8e\u5f52\u5e76\u7684\u64cd\u4f5c\u3002 \u8fd9\u6837\u6211\u4eec\u5c31\u6709\u4e86\u4e00\u4e2a \\(O(n^2logn)\\) \u7684\u300c\u9ad8\u300d\u6548\u505a\u6cd5\u3002 <\/p>\n\n\n\n
\u600e\u4e48\u4f18\u5316\u8fd9\u4e2a\u505a\u6cd5\u5462\uff1f \u6211\u4eec\u4e0d\u59a8\u8003\u8651\u91cd\u94fe\u5256\u5206\u542f\u53d1\u5f0f\u5408\u5e76\u3002\u8fd9\u6837\u5c31\u5c06\u590d\u6742\u5ea6\u4f18\u5316\u5230\u4e86 \\(O(nlog^2n)\\) \uff0c\u8db3\u4ee5\u901a\u8fc7\u6b64\u9898\u3002 \u5177\u4f53\u6765\u8bf4\uff0c\u6211\u4eec\u5bf9\u4e8e\u6bcf\u4e2a\u8282\u70b9\u5f00\u4e00\u4e2amap\uff0c\u7136\u540e\u66b4\u529b\u5408\u5e76\u3002<\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\n#include<map>\n#include<set>\nusing namespace std;\nconst int N=200005;\nstruct ee{\n\tint v;\n\tint nxt;\n}e[N];\nint h[N],et=0;\ninline void add(int U,int V){\n\te[++et]=(ee){V,h[U]};\n\th[U]=et;\n}\nint w[N],sz[N],sn[N],dep[N],fa[N];\nint id[N];\nmultiset<int> lst[N];\nint n;\ninline void dfs0(int X){\n\tsn[X]=0,sz[X]=1;\n\tfor(int i=h[X];i;i=e[i].nxt){\n\t\tdfs0(e[i].v);\n\t\tsz[X]+=sz[e[i].v];\n\t\tif(sz[sn[X]]<sz[e[i].v]){\n\t\t\tsn[X]=e[i].v;\n\t\t}\n\t}\n}\ninline void dfs1(int X){\n\tif(sn[X]){\n\t\tdfs1(sn[X]);\n\t\tid[X]=id[sn[X]];\n\t}\n\tfor(int i=h[X];i;i=e[i].nxt){\n\t\tif(e[i].v==sn[X]){\n\t\t\tcontinue;\n\t\t}\n\t\tdfs1(e[i].v);\n\t\tlst[id[X]].insert(lst[id[e[i].v]].begin(),lst[id[e[i].v]].end());\n\t}\n\tlst[id[X]].insert(w[X]);\n\tmultiset<int>::iterator it=lst[id[X]].lower_bound(w[X]);\n\tif(it!=lst[id[X]].begin()){\n\t\t--it;lst[id[X]].erase(it);\n\t}\n}\nvoid init(){\n\tscanf(\"%d\",&n);\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%d\",&w[i]);\n\t\tid[i]=i;\n\t}\n\tint x;\n\tfor(int i=2;i<=n;++i){\n\t\tscanf(\"%d\",&x);\n\t\tfa[i]=x;add(x,i);\n\t}\n\tdfs0(1);\n\tdfs1(1);\n\tprintf(\"%d\\n\",lst[id[1]].size());\n}\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u6211\u4eec\u5c1d\u8bd5\u7c7b\u6bd4\u5e8f\u5217\u4e0a\u7684\u60c5\u51b5\u6765\u770b\u8fd9\u4e00\u9898\u3002 \u5bf9\u4e8e\u5e8f\u5217\u4e0a\u7684\u60c5\u51b5\uff0c\u6211\u4eec\u7ef4\u62a4\u4e00\u4e2a\u96c6\u5408 \\(S\\) \uff0c\u5176\u4e2d \\(S_i\\) … <\/p>\n