\u8ba9\u6211\u4eec\u6765\u5206\u6790\u8fd9\u9053\u9898\u3002
\n\u6211\u4eec\u5f88\u5bb9\u6613\u5730\u53ef\u4ee5\u53d1\u73b0\uff0c\u5982\u679c\u4e00\u4e2a\u8282\u70b9\u662f\u672b\u7aef\u8282\u70b9\uff0c\u90a3\u4e48\u5b83\u80af\u5b9a\u662f\u7531\u5b83\u7956\u5148\u4e2d\u7684\u7b2c\u4e00\u4e2a\u8282\u70b9\u7ba1\u8f96\u66f4\u4f18\u3002
\n\u7531\u6b64\u6211\u4eec\u7ee7\u7eed\u63a8\u5bfc\uff0c\u53ef\u4ee5\u53d1\u73b0\uff0c\u5047\u5982\u53ea\u6709\u4e24\u4e2a\u5173\u952e\u70b9\u7684\u8bdd\uff0c\u5b83\u4eec\u4e4b\u95f4\u7684\u94fe\u4e0a\u4e00\u5b9a\u53ef\u4ee5\u627e\u5230\u4e00\u4e2a\u5206\u754c\u7ebf\uff0c\u4f7f\u5f97\u8fd9\u6761\u5206\u754c\u7ebf\u7684\u4e00\u6bb5\u2014\u2014\u4ee5\u53ca\u6240\u6709\u4e0e\u94fe\u4e0a\u8fd9\u4e00\u7aef\u76f8\u90bb\u7684\u8282\u70b9\u2014\u2014\u653e\u5728\u4e00\u4e2a\u5173\u952e\u70b9\u4e0a\uff0c\u5e76\u628a\u5269\u4e0b\u7684\u653e\u5728\u53e6\u4e00\u4e2a\u5173\u952e\u70b9\u4e0a\u3002\u8fd9\u6837\u662f\u6700\u4f18\u7684\u3002
\n\u7136\u540e\u6211\u4eec\u8003\u8651\u6709\u4e09\u4e2a\u5173\u952e\u70b9\u7684\u60c5\u51b5\u3002\u5982\u679c\u6709\u4e09\u4e2a\u5173\u952e\u70b9\u7684\u8bdd\uff0c\u95ee\u9898\u4f3c\u4e4e\u5c31\u590d\u6742\u4e86\u5f88\u591a\uff0c\u8fd9\u662f\u56e0\u4e3a\u8fd9\u6761\u5206\u754c\u7ebf\u5fc5\u987b\u662f\u57fa\u4e8e\u4e09\u4e2a\u8282\u70b9\u5171\u540c\u51b3\u5b9a\u7684\u3002
\n\u6211\u4eec\u6362\u4e00\u4e2a\u601d\u8def\u8003\u8651\u3002\u6c42\u51fa\u4e09\u4e2a\u5173\u952e\u70b9\u4e24\u4e24\u7684LCA\u3002\u90a3\u4e48\uff0c\u8fd9\u4e00\u5206\u754c\u7ebf\u5c31\u5fc5\u7136\u53ef\u4ee5\u5728\u8fd9\u516d\u4e2a\u70b9\uff08\u6700\u591a\u516d\u4e2a\uff09\u4e24\u4e24\u4e4b\u95f4\u7684\u94fe\u4e0a\u627e\u5230\u3002
\n\u5b58\u5728\u4e00\u79cd\u53eb\u505a\u300c\u865a\u6811\u300d\u7684\u6570\u636e\u7ed3\u6784\u3002\u8fd9\u4e2a\u6570\u636e\u7ed3\u6784\u672c\u8d28\u4e0a\u5c31\u662f\u5c06\u6240\u6709\u5173\u952e\u70b9\u4ee5\u53ca\u5173\u952e\u70b9\u4e24\u4e24\u4e4b\u95f4\u7684LCA\u5efa\u6210\u4e00\u4e2a\u6570\u3002
\n\u6211\u4eec\u5982\u6b64\u8003\u8651\uff0c\u5982\u679c\u6709\u4e00\u4e2a\u70b9\u662f\u5173\u952e\u70b9\uff0c\u90a3\u4e48\u5b83\u5411\u4e0b\u80fd\u591f\u7ba1\u8f96\u7684\u70b9\u7684\u6570\u91cf\u5c31\u662f\u5b83\u7684\u5b50\u6811\u5927\u5c0f\u51cf\u53bb\u5b83\u7684\u6240\u6709\u5b50\u8282\u70b9\u80fd\u7ba1\u8f96\u7684\u70b9\u6570\u4e4b\u548c\u3002
\n\u5b83\u5411\u4e0a\u80fd\u591f\u7ba1\u8f96\u7684\u70b9\u7684\u6570\u91cf\u5219\u76f8\u5bf9\u6bd4\u8f83\u590d\u6742\u3002
\n\u6211\u4eec\u8003\u8651\u6bcf\u4e00\u6761\u8fb9\uff0c\u5047\u8bbe\u6211\u4eec\u5df2\u7ecf\u9884\u5904\u7406\u51fa\u4e86\u865a\u6811\u4e0a\u6bcf\u4e00\u4e2a\u70b9\u76f8\u90bb\u6700\u8fd1\u7684\u5173\u952e\u70b9\uff0c\u90a3\u4e48\uff0c\u5982\u679c\u8fd9\u6761\u8fb9\u4e24\u7aef\u7684\u70b9\u76f8\u90bb\u6700\u8fd1\u7684\u5173\u952e\u70b9\u662f\u76f8\u540c\u7684\uff0c\u90a3\u4e48\u8fd9\u6761\u8fb9\uff08\u4ee5\u53ca\u548c\u8fd9\u6761\u8fb9\u76f8\u90bb\u7684\u6240\u6709\u70b9\uff09\u90fd\u5212\u5f52\u5230\u90a3\u4e2a\u5173\u952e\u70b9\u4e0b\u7ba1\u8f96\u3002
\n\u5982\u679c\u8fd9\u6761\u8fb9\u4e24\u6bb5\u7684\u70b9\u76f8\u90bb\u6700\u8fd1\u7684\u5173\u952e\u70b9\u4e0d\u540c\uff0c\u5219\u9700\u8981\u4f7f\u7528\u500d\u589e\u6765\u786e\u5b9a\u8fd9\u6761\u8fb9\u8981\u5982\u4f55\u88ab\u5212\u5206\u6210\u4e24\u4e2a\u90e8\u5206\u3002<\/p>\n\n\n\n
\u63a5\u4e0b\u6765\u8981\u8003\u8651\u5982\u4f55\u786e\u5b9a\u865a\u6811\u4e0a\u6bcf\u4e00\u4e2a\u70b9\u76f8\u90bb\u6700\u8fd1\u7684\u5173\u952e\u70b9\u3002
\n\u6211\u4eec\u4e0d\u59a8\u8fd9\u6837\u8003\u8651\uff1a\u4e00\u4e2a\u70b9\u76f8\u90bb\u6700\u8fd1\u7684\u5173\u952e\u70b9\u5982\u679c\u5728\u5b83\u7684\u4e0b\u65b9\uff0c\u90a3\u4e48\u8fd9\u53ef\u4ee5\u901a\u8fc7\u6811\u5f62DP\u6c42\u5f97\uff1b\u5982\u679c\u5728\u5b83\u7684\u4e0a\u65b9\u6216\u8005\u5176\u4ed6\u5b50\u6811\u5185\u5462\uff1f
\n\u663e\u7136\uff0c\u5982\u679c\u8fd9\u4e2a\u70b9\u7684\u76f8\u90bb\u6700\u8fd1\u5173\u952e\u70b9\u5728\u5b83\u7684\u4e0a\u65b9\u6216\u8005\u548c\u5b83\u4e0d\u5728\u540c\u4e00\u5b50\u6811\u5185\uff0c\u90a3\u4e48\u5b83\u7684\u7236\u4eb2\u7684\u6700\u8fd1\u5173\u952e\u70b9\u4e00\u5b9a\u4e0e\u8fd9\u4e2a\u70b9\u7684\u6700\u8fd1\u5173\u952e\u70b9\u76f8\u540c\u3002
\n\u4e8e\u662f\uff0c\u6211\u4eec\u4e0d\u59a8\u4ece\u4e0a\u800c\u4e0bDP\uff0c\u6c42\u5f97\u8fd9\u4e2a\u70b9\u5728\u4e0a\u65b9\u6216\u8005\u4e0d\u5728\u540c\u4e00\u5b50\u6811\u7684\u6700\u8fd1\u5173\u952e\u70b9\u3002<\/p>\n\n\n\n
\u73b0\u5728\u6211\u4eec\u6765\u68b3\u7406\u4e00\u4e0b\u8fd9\u4e00\u9898\u7684\u601d\u8def\u3002
\n\u9996\u5148\uff0c\u6211\u4eec\u8fdb\u884c\u9884\u5904\u7406\uff0c\u5904\u7406\u51fa\u6bcf\u4e2a\u70b9\u7684\u6df1\u5ea6\u548cdfn\u3002
\n\u7136\u540e\uff0c\u6211\u4eec\u8fdb\u884c\u4e24\u6b21\u6811\u5f62DP\uff0c\u6c42\u51fa\u6bcf\u4e2a\u70b9\u7684\u6700\u8fd1\u5173\u952e\u70b9\u3002
\n\u7b2c\u4e09\uff0c\u6211\u4eec\u9884\u5904\u7406\u51fa\u6240\u6709\u300c\u672b\u7aef\u8282\u70b9\u300d\u2014\u2014\u4e5f\u5c31\u662f\u6240\u6709\u300c\u662f\u4e00\u4e2a\u865a\u6811\u4e0a\u8282\u70b9\u7684\u76f4\u63a5\u513f\u5b50\u4e14\u5b50\u6811\u5185\u6ca1\u6709\u5173\u952e\u70b9\u7684\u539f\u6811\u4e0a\u7684\u70b9\u300d\u3002\u8fd9\u4e9b\u70b9\u7684\u8d21\u732e\u53ef\u4ee5\u76f4\u63a5\u7edf\u8ba1\u5230\u5b83\u4eec\u7236\u4eb2\u7684\u6700\u8fd1\u5173\u952e\u70b9\u3002
\n\u6700\u540e\uff0c\u6211\u4eec\u4f9d\u6b21\u8003\u8651\u5269\u4e0b\u7684\u865a\u6811\u8fb9\u4e0a\u7684\u70b9\u3002\u5982\u679c\u4e24\u6bb5\u7684\u6700\u8fd1\u5173\u952e\u70b9\u76f8\u540c\uff0c\u90a3\u4e48\u5c31\u7edf\u8ba1\u5230\u90a3\u4e2a\u6700\u8fd1\u5173\u952e\u70b9\u3002\u5426\u5219\u5c31\u8fdb\u884c\u500d\u589e\u5bfb\u627e\u7b54\u6848\u3002 <\/p>\n\n\n\n
\u987a\u4fbf\u8bb2\u4e00\u4e0b\u5982\u4f55\u5efa\u865a\u6811\u3002
\n\u6211\u4eec\u5c06\u6240\u6709\u5173\u952e\u70b9\u6309\u7167dfs\u5e8f\u6392\u5e8f\uff0c\u7136\u540e\u5efa\u4e00\u4e2a\u6808\uff0c\u4ee3\u8868\u5f53\u524d\u6b63\u5728\u5411\u4e0b\u5ef6\u957f\u7684\u94fe\u3002
\n\u5982\u679c\u5f53\u524d\u7684\u70b9\u4e0e\u6808\u9876\u7684LCA\u7684\u6df1\u5ea6\u5c0f\u7b49\u4e8e\u6b21\u6808\u9876\uff0c\u90a3\u4e48\u5c31\u8bf4\u660e\u5f53\u524d\u70b9\u4e0d\u5728\u6808\u9876\u7684\u5b50\u6811\u91cc\uff0c\u4e5f\u5c31\u610f\u5473\u7740\u6808\u9876\u5904\u4e8e\u5f53\u524d\u5e94\u8be5\u7ef4\u62a4\u7684\u94fe\u5916\u3002
\n\u4e8e\u662f\uff0c\u6211\u4eec\u9700\u8981\u5c31\u53ef\u4ee5\u5c06\u65b0\u7684\u8fd9\u4e2a\u70b9\u52a0\u5165\u865a\u6811\u548c\u6808\u4e2d\u3002
\n\u5426\u5219\uff0c\u5c31\u8bf4\u660e\u539f\u6765\u7684\u6808\u9876\u9700\u8981\u88ab\u5f39\u51fa\uff0c\u90a3\u4e48\u5c31\u5904\u7406\u5b8c\u5b83\u5e94\u8be5\u8fde\u7684\u8fb9\u7136\u540e\u5c06\u5b83\u5f39\u51fa\u3002<\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\n#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)\n#define Fv2(i,X) for(int i=g[X];i;i=e[i].nxt)\nusing namespace std;\n\ntypedef pair<int,int> pii;\nconst int N=300005;\nconst int INF=0x3f3f3f3f;\nstruct ee{\n\tint v;\n\tint nxt;\n}e[1200005];\nint h[N],g[N],et=0;\ninline void add(int *H,int U,int V){\n\te[++et]=(ee){V,H[U]};\n\tH[U]=et;\n}\n\nint dfn[N],cnt=0,sz[N],dep[N],fa[N][20];\ninline void dfs0(int X){\n\tdfn[X]=++cnt;sz[X]=1;\n\tFv(i,X){\n\t\tif(e[i].v==fa[X][0]){\n\t\t\tcontinue;\n\t\t}\n\t\tfa[e[i].v][0]=X;dep[e[i].v]=dep[X]+1;\n\t\tdfs0(e[i].v);\n\t\tsz[X]+=sz[e[i].v];\n\t}\n}\nint usd[N],pt[N],ppt[N],hr[N],ans[N],up[N];\npii nr[N];\ninline void dfs1(int X){\n\tnr[X]=(usd[X]?pii(0,X):pii(INF,0));\n\tFv2(i,X){\n\t\tdfs1(e[i].v);\n\t\tnr[X]=min(nr[X],pii(nr[e[i].v].first+dep[e[i].v]-dep[X],nr[e[i].v].second));\n\t}\n}\ninline void dfs2(int X,int D,int P){\n\tif(pii(D,P)<nr[X]){\n\t\tnr[X]=pii(D,P);\n\t}else{\n\t\tD=nr[X].first,P=nr[X].second;\t\n\t}\n\tFv2(i,X){\n\t\tdfs2(e[i].v,D+dep[e[i].v]-dep[X],P);\n\t}\n}\n\/\/\u5b50\u8282\u70b9\u4e2d\u6240\u6709\u5b50\u6811\u4e2d\u6709\u865a\u6811\u4e0a\u8282\u70b9\u7684\u70b9\u90fd\u662f\u4e0d\u53ef\u4ee5\u9009\u53d6\u7684\u3002\n\/\/\u6211\u4eec\u4e0d\u59a8\u9006\u5411\u8003\u8651\uff0c\u679a\u4e3e\u6bcf\u4e00\u4e2a\u865a\u6811\u4e0a\u7684\u5b50\u8282\u70b9\uff0c\u7136\u540e\u4ece\u90a3\u4e2a\u8282\u70b9\u5f00\u59cb\u500d\u589e\uff0c\u4e00\u76f4\u500d\u589e\u5230\u8fd9\u68f5\u6811\u7684\u5b50\u8282\u70b9\uff0c\u7136\u540e\u628a\u8fd9\u4e9b\u5b50\u8282\u70b9\u7684\u5b50\u6811\u6316\u6389\u3002 \ninline void dfs3(int X){\n\tans[hr[X]=nr[X].second]+=sz[X];\n\tFv2(i,X){\n\t\tint nw=e[i].v;\n\t\tfor(int j=18;j>=0;--j){\n\t\t\tif(fa[nw][j]&&dep[fa[nw][j]]>dep[X]){\n\t\t\t\tnw=fa[nw][j];\n\t\t\t}\n\t\t}\n\t\tans[hr[X]]-=sz[up[e[i].v]=nw];\n\t\tdfs3(e[i].v);\n\t}\n}\n\/\/\u73b0\u5728\u5269\u4e0b\u7684\u672b\u7aef\u8282\u70b9\u5c31\u53ea\u6709\u865a\u6811\u4e0a\u7684\u8282\u70b9\u4e86\u3002 \n\/\/\u5982\u679c\u5b50\u8282\u70b9\u7684dfs\u5e8f\u5927\u4e8e\u5f53\u524d\u8282\u70b9\uff0c\u90a3\u4e48\u5206\u5272\u70b9\u5c31\u504f\u4e0a\uff1b\u5426\u5219\u504f\u4e0b\u3002 \ninline void dfs4(int X){\n\tFv2(i,X){\n\t\tif(hr[e[i].v]==hr[X]){\n\t\t\tans[hr[X]]+=sz[up[e[i].v]]-sz[e[i].v];\n\t\t}else{\n\t\t\tint len=dep[hr[e[i].v]]+dep[X]-nr[X].first;\n\t\t\tlen=((len&1)?(len+1)>>1:((len>>1)+(int)(hr[e[i].v]>hr[X])));\n\/\/\t\t\t\u8fd9\u91cc\u6bd4\u8f83\u7684\u662f\u7f16\u53f7\uff01\uff01\uff01 \n\t\t\tint nw=e[i].v;\n\t\t\tfor(int j=18;j>=0;--j){\n\t\t\t\tif(dep[fa[nw][j]]>=len){\n\t\t\t\t\tnw=fa[nw][j];\n\t\t\t\t}\n\t\t\t}\n\t\t\tans[hr[e[i].v]]+=sz[nw]-sz[e[i].v];\n\t\t\tans[hr[X]]+=sz[up[e[i].v]]-sz[nw];\n\t\t}\n\t\tdfs4(e[i].v);\n\t}\n}\ninline void dfs5(int X){\n\tup[X]=hr[X]=0;\n\tFv2(i,X){\n\t\tdfs5(e[i].v);\n\t}\n\tg[X]=0;\n}\ninline bool cmp(int A,int B){\n\treturn dfn[A]<dfn[B];\n}\ninline int lca(int X,int Y){\n\tif(dep[X]<dep[Y]){\n\t\tswap(X,Y);\n\t}\n\tfor(int i=18;i>=0;--i){\n\t\tif(dep[fa[X][i]]>=dep[Y]){\n\t\t\tX=fa[X][i];\n\t\t}\n\t}\n\tif(X==Y){\n\t\treturn X;\n\t}\n\tfor(int i=18;i>=0;--i){\n\t\tif(fa[X][i]!=fa[Y][i]){\n\t\t\tX=fa[X][i],Y=fa[Y][i];\n\t\t}\n\t}\n\treturn fa[X][0];\n}\nint st[N],tp=0;\nvoid init(){\n\tint n,Q;\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(h,u,v);\n\t\tadd(h,v,u);\n\t}\n\tdep[1]=1;\n\tdfs0(1);\n\tfor(int j=1;j<=18;++j){\n\t\tfor(int i=1;i<=n;++i){\n\t\t\tfa[i][j]=fa[fa[i][j-1]][j-1];\n\t\t}\n\t}\n\tscanf(\"%d\",&Q);\n\tint m,X,Y;\n\twhile(Q--){\n\t\tscanf(\"%d\",&m);\n\t\tfor(int i=1;i<=m;++i){\n\t\t\tscanf(\"%d\",&pt[i]);\n\t\t\tppt[i]=pt[i],usd[pt[i]]=1;\n\t\t}\n\t\tsort(pt+1,pt+1+m,cmp);\n\t\tst[tp=1]=pt[1];\n\t\tfor(int i=2;i<=m;++i){\n\t\t\tX=pt[i],Y=lca(X,st[tp]);\n\t\t\twhile(tp>1&&dep[Y]<=dep[st[tp-1]]){\n\t\t\t\tadd(g,st[tp-1],st[tp]);\n\t\t\t\t--tp;\n\t\t\t}\n\t\t\tif(Y!=st[tp]){\n\t\t\t\tadd(g,Y,st[tp]);st[tp]=Y;\n\t\t\t}\n\t\t\tst[++tp]=X;\n\t\t}\n\t\twhile(tp>1){\n\t\t\tadd(g,st[tp-1],st[tp]);\n\t\t\t--tp;\n\t\t}\n\t\tdfs1(st[1]);\n\t\tdfs2(st[1],nr[st[1]].first,nr[st[1]].second);\n\t\tdfs3(st[1]);\n\t\tdfs4(st[1]);\n\t\tans[hr[st[1]]]+=sz[1]-sz[st[1]];\n\t\tfor(int i=1;i<=m;++i){\n\t\t\tprintf(\"%d \",ans[ppt[i]]);\n\t\t}\n\t\tputs(\"\");\n\t\tdfs5(st[1]);\n\t\tfor(int i=1;i<=m;++i){\n\t\t\tans[pt[i]]=0,usd[pt[i]]=0;\n\t\t}\n\t}\n}\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u8ba9\u6211\u4eec\u6765\u5206\u6790\u8fd9\u9053\u9898\u3002 \u6211\u4eec\u5f88\u5bb9\u6613\u5730\u53ef\u4ee5\u53d1\u73b0\uff0c\u5982\u679c\u4e00\u4e2a\u8282\u70b9\u662f\u672b\u7aef\u8282\u70b9\uff0c\u90a3\u4e48\u5b83\u80af\u5b9a\u662f\u7531\u5b83\u7956\u5148\u4e2d\u7684\u7b2c\u4e00\u4e2a\u8282\u70b9\u7ba1\u8f96\u66f4\u4f18 … <\/p>\n