[{"type":"Paragraph","children":[{"text":"o(nlogn)预处理，o(1)查询树任意两点之间的距离，o(1)查询树任意两点的最近公共祖先，o(n)求树的一组直径两个端点"}],"slateId":"HWORsBQCR93PHmYlNo3Vu"},{"type":"Heading2","slateId":"mYOVDfSws5-HKBRCz8nD0","children":[{"text":"封装模板"}]},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"//使用示例见模板下方\ntemplate struct Tree_theory{\n const vector* adj;\n int dfn[N]; \n int fa[N];\n int dep[N];\n int f[N][25];\n int clk=0,nn=0;\n void dfs_init(int u,int father,int deep){\n dfn[u]=++clk;\n dep[clk]=deep;\n fa[clk]=father;\n for(int to:adj[u]){\n if(to==father) continue;\n dfs_init(to,u,deep+1);\n }\n }\n int ask(int lo,int ro){\n int k=__lg(ro-lo+1);\n if(dep[f[lo][k]]adj[]){\n nn=_n;\n\t\tclk=0;\n\t this->adj=adj;\n dfs_init(1,0,0);\n for(int i=1;i<=_n;++i) f[i][0]=i;\n for(int j=1;(1< Diameter(){ //求树的直径两个端点\n int ver1=1,ver2=1,mx=0;\n for(int i=1;i<=nn;++i){\n int t=Dis(1,i);\n if(t>mx) mx=t,ver1=i;\n }\n mx=0;\n for(int i=1;i<=nn;++i){\n int t=Dis(ver1,i);\n if(t>mx) mx=t,ver2=i;\n }\n return {ver1,ver2};\n }\n};"}],"slateId":"tDRahPKDiUp8nBC4zLWG_"}],"slateId":"W-OTMw1-G2zvrcOtIDJqp"},{"type":"Heading2","children":[{"text":"使用示例"}],"slateId":"JzHJOn_SWTAkVv1xBCVFE"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include\nusing namespace std;\n/* 树论模板 */\ntemplate struct Tree_theory{\n const vector* adj;\n int dfn[N]; \n int fa[N];\n int dep[N];\n int f[N][25];\n int clk=0,nn=0;\n void dfs_init(int u,int father,int deep){\n dfn[u]=++clk;\n dep[clk]=deep;\n fa[clk]=father;\n for(int to:adj[u]){\n if(to==father) continue;\n dfs_init(to,u,deep+1);\n }\n }\n int ask(int lo,int ro){\n int k=__lg(ro-lo+1);\n if(dep[f[lo][k]]adj[]){\n nn=_n;\n\t\tclk=0;\n\t this->adj=adj;\n dfs_init(1,0,0);\n for(int i=1;i<=_n;++i) f[i][0]=i;\n for(int j=1;(1< Diameter(){ //求树的直径两个端点\n int ver1=1,ver2=1,mx=0;\n for(int i=1;i<=nn;++i){\n int t=Dis(1,i);\n if(t>mx) mx=t,ver1=i;\n }\n mx=0;\n for(int i=1;i<=nn;++i){\n int t=Dis(ver1,i);\n if(t>mx) mx=t,ver2=i;\n }\n return {ver1,ver2};\n }\n};\n/* 树论模板 */\nconst int maxn=2*1e5+20;\nTree_theory T;\nvector e[maxn]; //邻接表\nint mian(){\n int n;\n cin >> n; //树的总点数n\n for(int i=1;i<=n-1;++i){ //输入n-1条边建树\n int u,v;\n cin >> u >> v;\n e[u].push_back(v);\n e[v].push_back(u);\n }\n T.Run(n,e); // o(nlogn)初始化\n int lca_1_2=T.Lca(1,2); //o(1)求点1和2的最近公共祖先\n int dis_1_2=T.Dis(1,2); //o(1)求点1和2之间的距离\n pair diameter=T.Diameter(); //o(n)求树的直径的两个端点\n return 0;\n}"}],"slateId":"9E-8N2Pte_OgCG-RJQDvf"}],"slateId":"SMuJ0lmMUVZh6A-d9iGVH"}]