\u6309\u7167\u6211\u4eec\u4e4b\u524d\u7684\u7ecf\u9a8c\uff0c\u4ed9\u4eba\u638c\u4e0a\u95ee\u9898\u5f80\u5f80\u53ef\u4ee5\u901a\u8fc7\u5706\u65b9\u6811\u8f6c\u5316\u4e3a\u6811\u4e0a\u95ee\u9898\u3002
\n\u6211\u4eec\u53d1\u73b0\uff0c\u6700\u77ed\u8def\u5728\u6811\u4e0a\u662f\u4e00\u79cd\u975e\u5e38\u5bb9\u6613\u89e3\u51b3\u7684\u95ee\u9898\u3002\u53ea\u9700\u9884\u5904\u7406\u5230\u6839\u8282\u70b9\u7684\u957f\u5ea6\u7136\u540e\u6b7b\u547d\u8dd1LCA\u5c31\u53ef\u4ee5\u4e86\u3002
\n\u4f46\u662f\u5728\u4e00\u822c\u56fe\u4e0a\uff0c\u6700\u77ed\u8def\u7684\u5b9e\u65f6\u5904\u7406\u5c31\u4f1a\u53d8\u5f97\u5f88\u56f0\u96be\u3002
\n\u6211\u4eec\u53ef\u4ee5\u5c1d\u8bd5\u901a\u8fc7\u7ed9\u5706\u65b9\u6811\u4e0a\u7684\u8fb9\u8d4b\u4e0a\u7279\u522b\u7684\u8fb9\u6743\u6765\u5904\u7406\u8fd9\u4e2a\u95ee\u9898\u3002<\/p>\n\n\n\n
\u5bf9\u4e8e\u5706-\u5706\u8fb9\uff0c\u8d4b\u8fb9\u6743\u4e3a\u539f\u8fb9\u6743\uff0c\u8fd9\u662f\u5bb9\u6613\u7406\u89e3\u7684\u3002
\n\u5bf9\u4e8e\u65b9\u70b9\u5230\u5b83\u7684\u7236\u4eb2\u5706\u70b9\u7684\u8fb9\uff0c\u8d4b\u8fb9\u6743\u4e3a0\uff0c\u5bf9\u4e8e\u5706\u70b9\u5230\u5b83\u7684\u7236\u4eb2\u65b9\u70b9\u7684\u8fb9\uff0c\u8d4b\u8fb9\u6743\u4e3a\u8fd9\u4e2a\u5706\u70b9\u5230\u8fd9\u4e2a\u65b9\u70b9\u7684\u7236\u4eb2\u5706\u70b9\u7684\u6700\u77ed\u8ddd\u79bb\u3002 <\/p>\n\n\n\n
\u8fd9\u65f6\u5019\u6211\u4eec\u4f1a\u9047\u5230\u4e00\u4e2a\u95ee\u9898\uff0c\u5c31\u662fTarjan\u627e\u73af\u7684\u65f6\u5019\u627e\u4e0d\u5230\u8fd4\u7956\u8fb9\u7684\u8fb9\u6743\u3002
\n\u89e3\u51b3\u65b9\u6848\u662f\u8bb0\u5f55\u6bcf\u4e00\u4e2a\u5230\u6839\u8282\u70b9\u5728dfs\u6811\u4e0a\u7684\u8ddd\u79bb\uff0c\u7136\u540e\u5f53\u6211\u4eec\u627e\u5230\u4e00\u4e2a\u73af\u4e00\u8def\u627e\u7238\u7238\u5e76\u7edf\u8ba1\u957f\u5ea6\u5373\u53ef\u3002<\/p>\n\n\n\n
\u7136\u540e\u662f\u8ba1\u7b97\u7b54\u6848\uff0c\u6211\u4eec\u53d1\u73b0\uff0c\u5982\u679c\u8be2\u95ee\u7684\u4e24\u4e2a\u70b9\u7684\u6700\u8fd1\u516c\u5171\u7956\u5148\u662f\u4e00\u4e2a\u65b9\u70b9\uff0c\u90a3\u4e48\u5b83\u4eec\u7684\u7b54\u6848\u4e0d\u80fd\u7528\u666e\u901a\u65b9\u6cd5\u8ba1\u7b97\u3002
\n\u6211\u4e00\u5f00\u59cb\u7684\u60f3\u6cd5\u662f\u5c1d\u8bd5\u76f4\u63a5\u7528\u67d0\u4e2a\u8282\u70b9\u5230\u7236\u4eb2\u65b9\u70b9\u7684\u8fb9\u6743\u76f4\u63a5\u8ba1\u7b97\u7b54\u6848\uff0c\u4f46\u8fd9\u6837\u4f1a\u5bfc\u81f4\u7b54\u6848\u9519\u8bef\uff0c\u539f\u56e0\u662f\u5b83\u65e0\u6cd5\u6b63\u786e\u5730\u533a\u5206\u4e24\u4e2a\u70b9\u4f4d\u4e8e\u5706\u73af\u7684\u540c\u4e00\u4fa7\u8fd8\u662f\u4e0d\u540c\u4fa7\u7684\u60c5\u51b5\u3002
\n\u6545\u800c\uff0c\u6211\u4eec\u9700\u8981\u4fdd\u5b58\u539f\u6765\u7684\u8ddd\u79bb\u5b83\u7684\u7236\u4eb2\u65b9\u70b9\u7684\u9760\u67d0\u4e00\u4fa7\u7684\u8ddd\u79bb\uff0c\u6545\u800c\u5f53lca\u662f\u65b9\u70b9\u7684\u65f6\u5019\u7279\u6b8a\u5224\u65ad\u8ba1\u7b97\u5373\u53ef\u3002 <\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)\n\ntypedef long long ll;\n\ninline ll Min(ll A,ll B){\n return A<B?A:B;\n}\ninline int Min(int A,int B){\n\treturn A<B?A:B;\n}\ninline ll Abs(ll A){\n\treturn A>0?A:-A;\n}\ninline void Swap(int &A,int &B){\n A^=B^=A^=B;\n}\n\nstruct ee{\n int v;\n ll w;\n int nxt;\n}e[200005];\nint h0[10005],h[20005],et=0;\ninline void Eadd(int *H,int U,int V,ll W){\n e[++et]=(ee){V,W,H[U]};\n H[U]=et;\n}\ninline void add(int *H,int U,int V,ll W){\n Eadd(H,U,V,W);\n Eadd(H,V,U,W);\n}\nint dfn[20005],lw[20005],cnt=0,dep[20005],fa[20005][30];\nll dis[20005],sz[20005];\nint nm=0;\nint st[20005],tp=0;\ninline void dfs0(int X){\n dfn[X]=lw[X]=++cnt;\n Fv(h0,i,X){\n \tif(e[i].v==fa[X][0]){\n \t\tcontinue;\n\t\t}\n if(!dfn[e[i].v]){\n fa[e[i].v][0]=X;\n dis[e[i].v]=dis[X]+e[i].w;\n dfs0(e[i].v);\n lw[X]=Min(lw[X],lw[e[i].v]);\n \t}else{\n\t\t\tlw[X]=Min(lw[X],dfn[e[i].v]);\n\t\t\tif(e[i].v!=fa[X][0]&&dfn[e[i].v]<dfn[X]){\n ++nm;\n add(h,nm,e[i].v,0);\n ll len=e[i].w;\n for(int j=X;j^e[i].v;j=fa[j][0]){\n \tlen+=dis[j]-dis[fa[j][0]];\n }\n sz[nm]=len;\n ll nw=e[i].w;\n for(int j=X;j^e[i].v;j=fa[j][0]){\n add(h,nm,j,Min(nw,len-nw));\n sz[j]=nw; \n nw+=dis[j]-dis[fa[j][0]];\n }\n }\n }\n if(lw[e[i].v]>dfn[X]){\n \tadd(h,X,e[i].v,e[i].w);\n\t\t} \n }\n}\n\ninline void dfs1(int X,int FA){\n dep[X]=dep[FA]+1;\n fa[X][0]=FA;\n Fv(h,i,X){\n if(e[i].v!=FA){\n dis[e[i].v]=dis[X]+e[i].w;\n dfs1(e[i].v,X);\n }\n }\n}\n\nint n,m,q;\n\ninline ll calc(int X,int Y){\n int XX=X,YY=Y,lca;\n while(dep[XX]<dep[YY]){\n Swap(XX,YY);\n }\n for(int i=20;~i;--i){\n if(dep[XX]-(1<<i)>=dep[YY]){\n XX=fa[XX][i];\n }\n }\n if(XX==YY){\n lca=XX;\n }else{\n for(int i=20;~i;--i){\n if(fa[XX][i]!=fa[YY][i]){\n XX=fa[XX][i];\n YY=fa[YY][i];\n }\n }\n lca=fa[XX][0];\n }\n ll RT=dis[X]+dis[Y]-(dis[lca]<<1);\n if(lca>n){\n ll P=dis[XX]-dis[lca],Q=dis[YY]-dis[lca];\n RT-=(P+Q);\n RT+=Min(sz[lca]-Abs(sz[XX]-sz[YY]),Abs(sz[XX]-sz[YY]));\n }\n return RT;\n}\n\n\n\nvoid init(){\n scanf(\"%d%d%d\",&n,&m,&q);\n nm=n;\n int u,v;\n\tll w;\n for(int i=1;i<=m;++i){\n scanf(\"%d%d%lld\",&u,&v,&w);\n add(h0,u,v,w);\n }\n fa[1][0]=0;\n dfs0(1);\n for(int i=1;i<=nm;++i){\n dep[i]=0,dis[i]=0;\n }\n dfs1(1,0);\n for(int j=1;j<=20;++j){\n for(int i=1;i<=nm;++i){\n fa[i][j]=fa[fa[i][j-1]][j-1];\n }\n }\n int x,y;\n for(int i=1;i<=q;++i){\n scanf(\"%d%d\",&x,&y);\n printf(\"%lld\\n\",calc(x,y));\n }\n}\nint main(){\n init();\n return 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u6309\u7167\u6211\u4eec\u4e4b\u524d\u7684\u7ecf\u9a8c\uff0c\u4ed9\u4eba\u638c\u4e0a\u95ee\u9898\u5f80\u5f80\u53ef\u4ee5\u901a\u8fc7\u5706\u65b9\u6811\u8f6c\u5316\u4e3a\u6811\u4e0a\u95ee\u9898\u3002 \u6211\u4eec\u53d1\u73b0\uff0c\u6700\u77ed\u8def\u5728\u6811\u4e0a\u662f\u4e00\u79cd\u975e\u5e38\u5bb9\u6613\u89e3\u51b3\u7684 … <\/p>\n