一直不熟练,有时间要多看几遍。
巡逻 树上dp+树的直径+思维
代码
1 | int dis[N], pre[N], head[N], nex[N<<1], ver[N<<1], edge[N<<1], vis[N]; |
LCA模板:求树上任意两点的距离
方法一:在线倍增 复杂度O((n+m)logn)
代码
1 | int f[N][20], d[N], dis[N]; |
方法二:离线tarjan 复杂度O(m+n)
代码
1 | int ver[N<<1], nex[N<<1], edg[N<<1], head[N]; |