求助树链全WA+TLE

P3379 【模板】最近公共祖先(LCA)

@[wangziwenhk](/user/727556) 虽然但是,你这个树剖是不是写的有点抽象啊
by Hoks @ 2024-03-27 17:02:46


@[wangziwenhk](/user/727556) 你疑似对子树大小 ```size``` 的定义有误解,子树大小应为子树点数,而不是儿子个数,且求lca时应比较两者 ```top``` 的深度。
by __Chx__ @ 2024-03-27 17:19:27


并且建议用 ```vector``` 存边,数组记录每个点的信息,使用 ```map``` 多一个 $\log$ 的复杂度。
by __Chx__ @ 2024-03-27 17:23:54


@[__Chx__](/user/753355) 感谢,已关
by wangziwenhk @ 2024-03-28 14:11:06


@[__Chx__](/user/753355) 但是 Sub1 #2还是T了 ```c++ #include <bits/stdc++.h> using namespace std; struct Node{ vector<int>child; int size,father,deep; int bestSon,top; }; array<vector<int>,500050>graph; array<Node,500050>tree; int n,m,s; int build(int x,int father,int deep){ tree[x].father = father; tree[x].deep = deep; int k=-1,v=-1,t; for(auto i:graph[x]){ if(i == father)continue; t = build(i,x,deep+1); if(t>v){ v = t; k = i; } tree[x].child.push_back(i); } tree[x].bestSon = k; tree[x].size = graph[x].size()+1; return tree[x].size; } void link(int x,int top){ tree[x].top = top; if(tree[x].bestSon==-1)return; for(auto i:tree[x].child){ if(tree[x].bestSon==i)link(i,top); else link(i,i); } } int lca(int x,int y){ while(tree[x].top != tree[y].top){ int tx = tree[x].top; int ty = tree[y].top; if(tree[tx].deep>tree[ty].deep){ if(tree[x].top == x)x = tree[x].father; else x = tree[x].top; } else{ if(tree[y].top == y)y = tree[y].father; else y = tree[y].top; } } return tree[x].deep > tree[y].deep ? y : x; } int main(){ scanf("%d%d%d",&n,&m,&s); for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); if(x==y)continue; graph[x].push_back(y); graph[y].push_back(x); } build(s,s,1); link(s,s); while(m--){ int x,y; scanf("%d%d",&x,&y); printf("%d\n", lca(x,y)); } } ```
by wangziwenhk @ 2024-03-28 14:32:08


@[wangziwenhk](/user/727556) ```size```的概念应该为子树的点数,此处 ```graph[x].size()+1```意为点 $x$ 的边数+1,应改为: ``` int build(int x,int father,int deep){ tree[x].father = father; tree[x].deep = deep; tree[x].size = 1; int k=-1,v=-1,t; for(auto i:graph[x]){ if(i == father)continue; t = build(i,x,deep+1); if(t>v){ v = t; k = i; } tree[x].size += t; tree[x].child.push_back(i); } tree[x].bestSon = k; return tree[x].size; } ```
by __Chx__ @ 2024-03-28 14:40:23


建议模板题可适当学习一些题解的优秀写法
by __Chx__ @ 2024-03-28 14:42:29


@[__Chx__](/user/753355) 懂了,谢谢
by wangziwenhk @ 2024-03-28 14:43:20


|