該題用離線算法的時候要注意會MLE， 內存卡的很緊， 所以要想辦法優化內存， 利用存儲邊的數組就行了。? LCA是利用了并查集在樹上進行的操作， 由于該題可能不形成一棵樹，所以要對所有子樹進行LCA。 然后不在一個集合中的兩個點不能聯通。 下面簡單說一下我對LCA的理解： LCA就是dfs+并查集優化。 ? 用dfs深搜， 當其回溯到結點u時， u的子樹已經全部搜尋完了， 并且用并查集將其子樹合并到了一個集合之中。 ?這時， 其子樹的最近公共祖先就是當前結點u。 ? 當然，其實我們也可以省略掉數組ancestor， 直接將最近公共祖先這個信息維護成并查集的根。 細節參見代碼： ~~~ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 10000+5; const int maxq = 1000000+5; int n,u,m,v,dist[maxn],k,answer[maxq],f[maxn],h[maxn],tt,q,head[maxn],tot; int _find(int x) { return f[x] == x ? x : f[x] = _find(f[x]); } void bing(int u, int v) { int t1 = _find(u); int t2 = _find(v); if(t1 != t2) f[t1] = t2; } bool vis[maxn]; struct Edge { int to, next, dist; }edge[maxn*2]; void addedge(int u, int v, ll dist) { edge[tot].to = v; edge[tot].dist = dist; edge[tot].next = head[u]; head[u] = tot++; } struct Query { int q, next, index; }query[maxq*2]; void add_query(int u, int v, int index) { query[tt].q = v; query[tt].next = h[u]; query[tt].index = index; h[u] = tt++; query[tt].q = u; query[tt].next = h[v]; query[tt].index = index; h[v] = tt++; } void init() { tot = tt = 0; for(int i=1;i<=n;i++) { h[i] = head[i] = -1; f[i] = i; vis[i] = false; } } void LCA(int u) { vis[u] = true; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(vis[v]) continue; dist[v] = dist[u] + edge[i].dist; LCA(v); bing(v, u); } for(int i = h[u]; i != -1; i = query[i].next) { int v = query[i].q; if(vis[v]) { answer[query[i].index] = _find(v); } } } int main() { while(~scanf("%d%d%d",&n,&m,&q)) { init(); for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&k); addedge(u, v, k); addedge(v, u, k); } for(int i=0;i<q;i++) { scanf("%d%d",&u,&v); add_query(u,v,i); } for(int i=1;i<=n;i++) { if(!vis[i]) { dist[i] = 0; LCA(i); } } for(int i=0;i<2*q;i+=2) { u = _find(query[i+1].q); v = _find(query[i].q); if(u != v) printf("Not connected\n"); else printf("%d\n",dist[query[i+1].q]-dist[answer[i/2]]+dist[query[i].q]-dist[answer[i/2]]); } } return 0; } ~~~