\u4ed9\u4eba\u638c\u56fe\u662f\u6bcf\u4e00\u4e2a\u70b9\u53cc\u90fd\u53ea\u6709\u4e00\u4e2a\u73af\u7684\u8fde\u901a\u56fe\u3002
\n\u5bf9\u4e8e\u4e00\u4e2a\u4ed9\u4eba\u638c\u56fe\uff0c\u5b83\u5728\u8bb8\u591a\u65b9\u9762\u90fd\u6709\u6811\u7684\u6027\u8d28\uff0c\u53ea\u662f\u5176\u4e2d\u7684\u6709\u4e00\u4e9b\u8282\u70b9\u88ab\u6362\u6210\u4e86\u73af\u3002
\n\u6211\u4eec\u4e0d\u59a8\u4f9d\u7136\u91c7\u7528\u4e00\u79cd\u4f2a\u6811\u5f62DP\u7684\u65b9\u5f0f\u6765\u5904\u7406\u8fd9\u68f5\u6811\uff0c\u6211\u4eec\u53d1\u73b0\uff0c\u975e\u73af\u8282\u70b9\u7684\u8f6c\u79fb\u90fd\u662f\u975e\u5e38\u5bb9\u6613\u8fbe\u6210\u4e86\uff0c\u95ee\u9898\u5728\u4e8e\u73af\u4e0a\u7684\u8282\u70b9\u7684\u8f6c\u79fb\u3002<\/p>\n\n\n\n
\u9996\u5148\uff0c\u6211\u4eec\u8981\u627e\u5230\u8fd9\u4e2a\u73af\uff0c\u8fd9\u53ef\u4ee5\u7528Tarjan\u7b97\u6cd5\u6765\u5b8c\u6210\u3002
\n\u5177\u4f53\u6765\u8bf4\uff0c\u6211\u4eec\u7ef4\u62a4\u4e24\u4e2a\u6570\u7ec4\uff1adfn\u548clw\uff0c\u5176\u4e2d\u524d\u8005\u8868\u793a\u7684\u662f\u67d0\u4e00\u4e2a\u8282\u70b9\u7684dfs\u5e8f\uff0c\u540e\u8005\u8868\u793a\u7684\u662f\u67d0\u4e00\u4e2a\u8282\u70b9\u81f3\u591a\u8d70\u4e00\u6761\u8fd4\u7956\u8fb9\u6216\u8005\u7236\u4eb2\u8fb9\u80fd\u591f\u5230\u8fbe\u7684\u6700\u5c0fdfs\u5e8f\u3002
\n\u663e\u7136\uff0c\u5728\u641c\u7d22\u4e2d\uff0c\u5982\u679c\u4e0b\u4e00\u4e2a\u8282\u70b9\u672a\u88ab\u8bbf\u95ee\u8fc7\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u5728\u641c\u7d22\u5b8c\u5b83\u4ee5\u540e\u5c06\u5f53\u524d\u8282\u70b9\u7684lw\u4e0e\u5b83\u7684lw\u53d6\u8f83\u5c0f\u503c\u3002
\n\u5426\u5219\uff0c\u5f53\u524d\u8282\u70b9\u901a\u5411\u5b83\u7684\u8fb9\u4e00\u5b9a\u662f\u4e00\u6761\u8fd4\u7956\u8fb9\u6216\u8005\u7236\u4eb2\u8fb9\uff0c\u90a3\u4e48\u5f53\u524d\u8282\u70b9\u7684lw\u503c\u5e94\u5f53\u4e0e\u5b83\u7684dfs\u5e8f\u53d6\u8f83\u5c0f\u503c\u3002 <\/p>\n\n\n\n
\u5bf9\u4e8e\u4e00\u4e2a\u73af\uff0c\u6211\u4eec\u5982\u679c\u5c06\u5b83\u89c6\u4e3a\u4e00\u4e2a\u8282\u70b9\uff0c\u6211\u4eec\u60f3\u4e00\u60f3\u8981\u600e\u4e48\u4ece\u5b83\u7684\u300c\u5b69\u5b50\u300d\u4eec\u5904\u8f6c\u79fb\u5462\uff1f
\n\u6211\u4eec\u53d1\u73b0\uff0c\u4f9d\u6b21\u679a\u4e3e\u5b83\u7684\u6bcf\u4e00\u4e2a\u5b69\u5b50\uff0c\u7b54\u6848\u663e\u7136\u662f\uff1a
\n$$max(f_i+f_j+dis_{i,j})$$
\n\u8fd9\u4e2a\u5f0f\u5b50\u53ef\u4ee5\u4f7f\u7528\u5355\u8c03\u961f\u5217\u4f18\u5316\u3002\u6240\u4ee5\u6211\u4eec\u6bcf\u4e00\u6b21\u628a\u4e00\u4e2a\u73af\u63d0\u51fa\u6765\u778eDP\u4e00\u4e0b\u5c31\u597d\u4e86\u3002 <\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<deque>\n#define Fv(A,U) for(int A=h[U];A;A=e[A].nxt)\n\ninline int Min(int A,int B){\n\treturn A<B?A:B;\n}\ninline int Max(int A,int B){\n\treturn A>B?A:B;\n}\n\nstruct ee{\n\tint v;\n\tint nxt;\n}e[200005];\nint et=0,h[100005];\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);\n\tEadd(V,U);\n}\n\nint n,m;\nint dfn[100005],lw[100005],dep[100005],fa[100005],cnt=0;\nint ans=0,f[100005],a[100005];\nstd::deque<int> q;\ninline void calc(int X,int Y){\n\tint tot=dep[Y]-dep[X]+1;\n\tint nw=tot;\n\tfor(int i=Y;i!=X;i=fa[i]){\n\t\ta[nw--]=f[i];\n\t}\n\ta[nw]=f[X];\n\tfor(int i=1;i<=tot;++i){\n\t\ta[tot+i]=a[i];\n\t}\n\twhile(!q.empty()){\n\t\tq.pop_front();\n\t}\n\tq.push_back(1);\n\tfor(int i=2;i<=(tot<<1);++i){\n\t\twhile(!q.empty()&&i-q.front()>(tot>>1)){\n\t\t\tq.pop_front();\n\t\t}\n\t\tif(!q.empty()){\n\t\t\tans=Max(ans,a[i]+a[q.front()]+i-q.front());\n\t\t}\n\t\twhile(!q.empty()&&a[q.back()]-q.back()<a[i]-i){\n\t\t\tq.pop_back();\n\t\t}\n\t\tq.push_back(i);\n\t}\n\tfor(int i=2;i<=tot;++i){\n\t\tf[X]=Max(f[X],a[i]+Min(i-1,tot-i+1));\n\t}\n}\ninline void dfs(int X,int FA){\n\tdfn[X]=lw[X]=++cnt;\n\tFv(i,X){\n\t\tif(e[i].v!=FA){\/\/\u8fd9\u4e00\u53e5\u5982\u679c\u4e0d\u52a0\u4f1a\u65e0\u5f62\u964d\u4f4e\u5f88\u591a\u70b9\u7684lw\u503c\uff0c\u4ece\u800c\u4f7f\u73af\u7684\u5927\u5c0f\u53d8\u62100\u3002 \n\t\t\tif(!dfn[e[i].v]){\n\t\t\t\tfa[e[i].v]=X;\n\t\t\t\tdep[e[i].v]=dep[X]+1;\n\t\t\t\tdfs(e[i].v,X);\n\t\t\t\tlw[X]=Min(lw[X],lw[e[i].v]);\n\t\t\t}else{\n\t\t\t\tlw[X]=Min(lw[X],dfn[e[i].v]);\n\t\t\t}\n\t\t\tif(lw[e[i].v]>dfn[X]){\n\t\t\t\tans=Max(ans,f[X]+f[e[i].v]+1);\n\t\t\t\tf[X]=Max(f[X],f[e[i].v]+1);\n\t\t\t}\n\t\t}\n\t\t\n\t}\n\tFv(i,X){\n\t\tif(fa[e[i].v]!=X&&dfn[X]<dfn[e[i].v]){\n\t\t\tcalc(X,e[i].v);\n\t\t}\n\t}\n}\n\nvoid init(){\n\tscanf(\"%d%d\",&n,&m);\n\tint u,v,x;\n\tfor(int i=1;i<=m;++i){\n\t\tu=0;\n\t\tscanf(\"%d\",&x);\n\t\tfor(int j=1;j<=x;++j){\n\t\t\tscanf(\"%d\",&v);\n\t\t\tif(u){\n\t\t\t\tadd(u,v);\n\t\t\t}\n\t\t\tu=v;\n\t\t}\n\t}\n\tdfs(1,0);\n\tprintf(\"%d\\n\",ans);\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u4ed9\u4eba\u638c\u56fe\u662f\u6bcf\u4e00\u4e2a\u70b9\u53cc\u90fd\u53ea\u6709\u4e00\u4e2a\u73af\u7684\u8fde\u901a\u56fe\u3002 \u5bf9\u4e8e\u4e00\u4e2a\u4ed9\u4eba\u638c\u56fe\uff0c\u5b83\u5728\u8bb8\u591a\u65b9\u9762\u90fd\u6709\u6811\u7684\u6027\u8d28\uff0c\u53ea\u662f\u5176\u4e2d\u7684\u6709\u4e00\u4e9b\u8282\u70b9\u88ab … <\/p>\n