题目大意
给出一棵树，起点，和要经过的点的序列，已经经过的点就不用去了，剩下的点按照顺序依次去，问要经过多少条边。
思路
链剖大概应该是可以，不过没试，用了听大爷说的一种神奇的方法。 因为树上经过的点肯定是一段一段的，就想到用并查集将一段合成一个点，，每个点最多只能被合一次，这样的话就能保证时间复杂度。查询的时候像链剖一样一段一段往上跳就行了，还要顺便把路径上的所有点缩起来。
CODE;int points, cross, start;int head[MAX], total;int _next[MAX << 1], aim[MAX << 1];inline void Add(int x, int y){_next[++total] = head[x];aim[total] = y;head[x] = total;}int deep[MAX];int father[MAX][20];void DFS(int x, int last){deep[x] = deep[last] + 1;for(int i = head[x]; i; i = _next[i]) {if(aim[i] == last) continue;father[aim[i]][0] = x;DFS(aim[i], x);}}void SparseTable(){for(int j = 1; j <= 19; ++j)for(int i = 1; i <= points; ++i)father[i][j] = father[father[i][j – 1]][j – 1];}inline pair<int, int> GetLCA(int x, int y){pair<int, int> re;if(deep[x] < deep[y]) swap(x, y);for(int i = 19; ~i; –i)if(deep[father[x][i]] >= deep[y]) {re.second += 1 << i;x = father[x][i];}if(x == y) {re.first = x;return re;}for(int i = 19; ~i; –i)if(father[x][i] != father[y][i]) {re.second += 1 << (i + 1);x = father[x][i];y = father[y][i];}re.first = father[x][0];re.second += 2;return re;}namespace UnionFindSet{int father[MAX];int Find(int x) {if(father[x] == x) return x;return father[x] = Find(father[x]);}}inline void Work(int x, int y, int lca){using namespace UnionFindSet;x = Find(x), y = Find(y);while(x != y) {if(deep[Find(::father[x][0])] < deep[Find(::father[y][0])]) swap(x, y);UnionFindSet::father[x] = ::father[x][0];x = Find(x);}if(x == lca)UnionFindSet::father[lca] = ::father[lca][0] ? ::father[lca][0]:points + 1;}int main(){cin >> points >> cross >> start;for(int x, y, i = 1; i < points; ++i) {scanf(“%d%d”, &x, &y);Add(x, y), Add(y, x);}DFS(1, 0);SparseTable();for(int i = 1; i <= points; ++i)UnionFindSet::father[i] = i;long long ans = 0;int now = start;for(int x, i = 1; i <= cross; ++i) {scanf(“%d”, &x);int fx = UnionFindSet::Find(x);if(fx != x) continue;pair<int ,int> re = GetLCA(x, now);ans += re.second;Work(x, now, re.first);now = x;}cout << ans << endl;return 0;}
我知道我不是一个很好的记录者，但我比任何人都喜欢回首自己来时的路，
