题解 P1196 【银河英雄传说】

其实思路和楼下差不多，也是维护一个前面和一个后面的人的个数，用后面的个数更新前面的个数，用前面的个数在Get\_Father中统计答案即可。 但是我直接在路径压缩里面直接把父亲压到了根节点上，于是我们的front的值不需要额外再在从当前的点更新到链上，于是就可以把路径压得更快。算个优化吧 ```cpp #include <cstdio> #include <cctype> #define MAXN 60000 using namespace std; inline char get_char(){ static char buf[1000001], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1 ++; } inline int read(){ int num = 0; char c; while (isspace(c = get_char())); while (num = num * 10 + c - 48, isdigit(c = get_char())); return num; } inline char get_ch(){ char c; while(!isalpha(c = get_char())); return c; } inline void swap(int &a,int &b){ int t = a; a = b; b = t; } int father[MAXN], front[MAXN], back[MAXN]; inline int Get_Father(int u){ if(u == father[u]) return u; int fa = Get_Father(father[u]); front[u] += front[father[u]];//中间的关系应该是累加的 father[u] = father[fa];//直接压缩在根上 return fa; } inline void Merge(int u, int v){ u = Get_Father(u), v = Get_Father(v); front[u] = back[v] + 1;//此时front已更新 back[v] += back[u] + 1;//所以通过back更新 father[u] = v; } inline int Query(int u, int v){ int fu = Get_Father(u), fv = Get_Father(v); if(fu != fv) return -1; int valu = front[u], valv = front[v];//直接压到了根，所以直接去front即可 if(valu < valv) swap(valu, valv); return valu - valv - 1;//减去重复 } int main(){ int n = read(); for(int i = 1; i <= 30000; i++) father[i] = i; for(int i = 1; i <= n; i++){ char con = get_ch(); int x = read(), y = read(); if(con == 'M') Merge(x, y); else printf("%d\n", Query(x, y)); } return 0; } ```