景区导游（LCA详解）

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 5;

int fa[N][21], deep[N];

vector<int> tree[N], tep[N];

ll path[N];

int n, k, mapp[N];

void dfs(int now, int father)//now表示当前顶点,father表示父节点

{

deep[now] = deep[father] + 1;//深度更新

fa[now][0] = father;//令当今节点的往上一步找到它的父亲

for (int i = 1; i <= 20; i++)//倍增每次都是走的2^i

{

fa[now][i] = fa[fa[now][i - 1]][i - 1];

}

int len = tree[now].size();

for (int i = 0; i < len; i++)//找出现在节点下所有的子节点

{

if (tree[now][i] == father) continue;//当找到的节点和父节点相同时跳过这个节点只找子节点

path[tree[now][i]] = path[now] + tep[now][i];//路径时间更新

dfs(tree[now][i], now);

}

}

int lca(int u, int v)//u表示起始节点v表示下一个节点

{

if (deep[u] <= deep[v])//如果起始节点深度小于下一节点深度交换两个节点v表示起始节点，u表示下一节点

{

swap(u, v);

}

for (int i = 20; i >= 0; i--)

{

if (deep[fa[u][i]] >= deep[v])

{

u = fa[u][i];

}

}//不在同一深度,开始向上跳如果u的父节点深度大于v的父节点深度则更新u的位置直到u与v在同一深度

if (u == v)

{

return u;//如果起始节点和下一节点一样代表已经是共同的祖先了

}

for (int i = 20; i >= 0; i--)

{

if (fa[u][i] != fa[v][i])

{

u = fa[u][i];

v = fa[v][i];

}

}//如果已经在同一深度了去找公共的祖先

return fa[u][0];

}//至此lca模板结束

ll path_distingush(int x1, int x2)//注意：函数要用longlong不然会超出范围

{

if (!x1 || !x2) return 0;

return path[x1] + path[x2] - 2 * path[lca(x1, x2)];//一定要去重到达公共祖先点的时候x1走了一次x2走了一次所有是去两次重

}

int main()

{

cin >> n >> k;

for (int i = 1; i < n; i++)

{

int u, v, t;

cin >> u >> v >> t;

tree[u].push_back(v);//无向图双向都可以走

tep[u].push_back(t);

tree[v].push_back(u);

tep[v].push_back(t);

}

dfs(1, 0);

ll ans = 0;

for (int i = 1; i <= k; i++)

{

cin >> mapp[i];

ans += path_distingush(mapp[i - 1], mapp[i]);

}

for (int i = 1; i <= k; i++)

{

cout << ans - path_distingush(mapp[i - 1], mapp[i]) - path_distingush(mapp[i], mapp[i + 1]) + path_distingush(mapp[i - 1], mapp[i + 1]) << ' ';

}//在原来要走的时间上减去要去的点就行了这个点的前后都要减，由于多减一段在i-1和i+1之间的时间先所以后面要加回来

}