1. 倍增的思想（基于二进制拼凑的思想）
倍增法最重要的思想就是根据二进制思想加上fa和depth数组去实现
fa[][] 数组
depth[] 数组
2：tarjan 离线算法（类似缩点的原理）
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void add(int from,int to,int w)
{
e[tot].to = to, e[tot].nxt = h[from], e[tot].w = w;
h[from] = tot ++;
}
void dfs(int u,int fa)
{
for(int i = h[u]; ~i; i = e[i].nxt)
{
int to = e[i].to;
if(to == fa) continue;
dis[to] = dis[u] + e[i].w;
dfs(to,u);
}
}
void tarjan(int u)
{
vis[u] = 1;
for(int i = h[u]; ~i; i = e[i].nxt)
{
int to = e[i].to;
if(!vis[to])
{
tarjan(to);
fa[to] = u;
}
}
for(auto nod : query[u])
{
int id = nod.second, y = nod.first;
if(vis[y] == 2)
{
res[id] = dis[y] + dis[u] - 2 * dis[find(y)];
}
}
vis[u] = 2;
}
京公网安备 11010502036488号