\u9996\u5148\u4ecb\u7ecd\u4e00\u4e0b\u6211\u4eec\u4eb2\u7231\u7684dsu on tree\uff0c\u4e5f\u5c31\u662f\uff08\u4e00\u79cd\uff1f\uff09\u6811\u4e0a\u542f\u53d1\u5f0f\u5408\u5e76\u3002
\n\u5b83\u672c\u8d28\u4e0a\u5c31\u662f\u4e00\u79cd\u4f18\u5316\u7684\u66b4\u529b\uff1a\u5bf9\u4e8e\u6811\u4e0a\u7684\u4fe1\u606f\uff0c\u6211\u4eec\u5148\u628a\u6811\u4ee5\u67d0\u79cd\u65b9\u5f0f\u5256\u5206\uff0c\u7136\u540e\u5bf9\u4e8e\u5173\u952e\u94fe\u76f4\u63a5\u4e0a\u4f20\uff0c\u975e\u5173\u952e\u94fe\u66b4\u529b\u5408\u5e76\u3002
\n\u5176\u4e2d\uff0c\u957f\u94fe\u5256\u5206\u4e00\u822c\u7528\u6765\u7ef4\u62a4\u548c\u6df1\u5ea6\u76f8\u5173\u7684\u4fe1\u606f\u3002
\n\u590d\u6742\u5ea6\u662fO(n)\u7684\u3002\u8bc1\u660e\u6211\u4e0d\u592a\u4f1a\u3002
\n\u5728\u8fd9\u4e00\u9898\u4e2d\uff0c\u6211\u4eec\u8003\u8651\u66b4\u529b\u7ef4\u62a4\u6bcf\u4e2a\u70b9\u4e3a\u6839\u7684\u5b50\u6811\u4e2d\u6bcf\u4e00\u5c42\u7684\u4fe1\u606f\uff0c\u5e76\u628a\u975e\u957f\u513f\u5b50\u7684\u4fe1\u606f\u5408\u5e76\u5230\u957f\u513f\u5b50\u4e2d\u3002
\n\u4e3a\u4e86\u4fdd\u8bc1\u7ebf\u6027\uff0c\u6211\u4eec\u4f7f\u7528\u6307\u9488\u3002
\n\u6211\u4eec\u5efa\u4e00\u4e2a\u6307\u9488\u6570\u7ec4f\uff0c\u5176\u4e2df_{i,j}\u8868\u793a\u4ee5i\u4e3a\u6839\u7684\u6839\u8282\u70b9\u7684\u5b50\u6811\u4e2d\u5230i\u7684\u8ddd\u79bb\u4e3aj\u7684\u8282\u70b9\u7684\u4e2a\u6570\u3002
\n\u540c\u65f6\u5efa\u4e00\u4e2a\u6570\u7ec4tmp\uff0c\u90a3\u4e48f\u5c31\u53d8\u6210\u6307\u5411\u7684\u662ftmp\u91cc\u9762\u7684\u503c\u3002\u8fd9\u6837\u5b50\u5c31\u53ef\u4ee5O(1)\u5408\u5e76\u975e\u957f\u513f\u5b50\u7684\u4fe1\u606f\u4e86\u3002\u56e0\u4e3a\\sigma len<=n\uff0c\u6240\u4ee5\u7a7a\u95f4\u662f\u8db3\u591f\u7684\u3002
\n\u90a3\u5c31\u6628\u665a\u4e86\u3002 <\/p>\n\n\n\n
<\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\n\nconst int N=1000005;\nstruct ee{\n\tint v;\n\tint nxt;\n}e[N<<1];\nint h[N],et=0;\ninline void Eadd(int U,int V){\n\te[++et]=(ee){V,h[U]};\n\th[U]=et;\n}\ninline void add(int U,int V){\n\tEadd(U,V);Eadd(V,U);\n}\nint n;\nint sn[N],len[N],ans[N],tmp[N],*f[N],*id=tmp;\ninline void dfs0(int X,int FA){\n\tsn[X]=0;\n\tfor(int i=h[X];i;i=e[i].nxt){\n\t\tif(e[i].v==FA){\n\t\t\tcontinue;\n\t\t}\n\t\tdfs0(e[i].v,X);\n\t\tif(len[sn[X]]<len[e[i].v]){\n\t\t\tsn[X]=e[i].v;\n\t\t}\n\t}\n\tlen[X]=len[sn[X]]+1;\n}\ninline void dfs1(int X,int FA){\n\tf[X][0]=1;\n\tif(sn[X]){\n\t\tf[sn[X]]=f[X]+1;\n\t\tdfs1(sn[X],X);\n\t\tans[X]=ans[sn[X]]+1;\n\t}\n\tfor(int i=h[X];i;i=e[i].nxt){\n\t\tif(e[i].v==FA||e[i].v==sn[X]){\n\t\t\tcontinue;\n\t\t}\n\t\tf[e[i].v]=id;id+=len[e[i].v];\n\t\tdfs1(e[i].v,X);\n\t\tfor(int j=1;j<=len[e[i].v];++j){\n\t\t\tf[X][j]+=f[e[i].v][j-1];\n\t\t\tif((j<ans[X]&&f[X][j]>=f[X][ans[X]])||(j>ans[X]&&f[X][j]>f[X][ans[X]])){\n\t\t\t\tans[X]=j;\n\t\t\t}\n\t\t}\n\t}\n\tif(f[X][ans[X]]==1){\n\t\tans[X]=0;\n\t}\n}\nvoid init(){\n\tscanf(\"%d\",&n);\n\tint u,v;\n\tfor(int i=1;i<n;++i){\n\t\tscanf(\"%d%d\",&u,&v);\n\t\tadd(u,v);\n\t}\n\tdfs0(1,0);\n\tf[1]=id;id+=len[1];\n\tdfs1(1,0);\n\tfor(int i=1;i<=n;++i){\n\t\tprintf(\"%d\\n\",ans[i]);\n\t} \n}\nint main(){\n\tinit();\n\treturn 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u9996\u5148\u4ecb\u7ecd\u4e00\u4e0b\u6211\u4eec\u4eb2\u7231\u7684dsu on tree\uff0c\u4e5f\u5c31\u662f\uff08\u4e00\u79cd\uff1f\uff09\u6811\u4e0a\u542f\u53d1\u5f0f\u5408\u5e76\u3002 \u5b83\u672c\u8d28\u4e0a\u5c31\u662f\u4e00\u79cd\u4f18\u5316\u7684\u66b4\u529b\uff1a\u5bf9 … <\/p>\n