记录下所有的提问,在建tarjan建一颗深搜树的时候询问。奇怪这道题的edge开4W会RE,,于是任性的开了40W妥妥过.
#include <stdio.h> #include <string.h> #include <algorithm> #include <vector> using namespace std; const int N = 400005; const int M = 205; struct node{ int v, w, nxt; }e[N]; struct pp{ int v, id; }p; vector <pp> ask[N]; int head[N]; int cnt; int vis[N]; int ans[N]; int n, m; int pre[N]; int dis[N]; void add(int u, int v, int w) { e[cnt].w = w; e[cnt].v = v; e[cnt].nxt = head[u]; head[u] = cnt++; } void init() { memset(vis, 0, sizeof(vis)); cnt = 0; memset(head, -1, sizeof(head)); for( int i = 1; i <= n; i ++ ) ask[i].clear(); for( int i = 1; i <= n; i++ ) pre[i] = i; memset(dis, 0, sizeof(dis)); memset(ans, -1, sizeof(ans)); } int find(int x) { return x == pre[x] ? x : pre[x] = find(pre[x]); } void tarjan(int u) { for( int i = head[u]; ~i; i = e[i].nxt ) { int to = e[i].v; if( !vis[to] ) { vis[to] = 1; dis[to] = dis[u] + e[i].w; tarjan(to); pre[to] = u; for( int j = 0; j < ask[to].size(); j++ ) { int v = ask[to][j].v; if( vis[v] && ans[ask[to][j].id] == -1 ) { if( v == to ) { ans[ask[to][j].id] = 0; } else { ans[ask[to][j].id] = dis[to] + dis[v] - 2 * dis[find(v)]; } } } } } } int main() { int tot; scanf("%d", &tot); while(tot--) { scanf("%d%d", &n, &m); init(); int u, v, w; for(int i = 1; i < n; i ++ ) { scanf("%d%d%d", &u, &v, &w); add(u, v, w); add(v, u, w); } for( int i = 1; i <= m; i ++ ) { scanf("%d%d", &u, &v); p.v = v, p.id = i; ask[u].push_back(p); p.v = u; ask[v].push_back(p); } vis[1] = 1; tarjan(1); for( int i = 1; i <= m; i ++ ) printf("%d\n", ans[i]); } return 0; }