1471
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <math.h> #include <limits.h> #pragma comment(linker, "/STACK:16777216") for C/C++ using namespace std; // Datatypes typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; // Define #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++) #define mp make_pair // Constants const double eps = 1e-8; const double PI = 3.1415926535897932384626433832795; #define INPUT_FILE "input.txt" #define OUTPUT_FILE "output.txt" vector< vector< ii > > tree; vector< bool > s; vector< int > c; int treeRoot = -1; void buildTree(int size) { tree.resize(size); s.resize(size); c.resize(size); } void addEdge(int u, int v, int w) { /* two edges */ tree[u].pb(mp(v,w)); tree[v].pb(mp(u,w)); } void assignRoot(int u) { treeRoot = u; } void dfs(int u, int w) { if(!s[u]) { /* not visited */ s[u] = true; c[u] = w; for(vector< ii >:: iterator it = tree[u].begin(); it != tree[u].end(); it ++) { if(!s[(*it).first]) { dfs((*it).first, w + (*it).second); } } } s[u] = false; } /* for LCA */ vi E; vi L; vi R; void init_lca(int n) { R.resize(n); E.reserve(2*n); L.reserve(2*n); } void dfs_lca(int u, int l) { if(!s[u]) { E.pb(u); L.pb(l); R[u] = sz(E)-1; /* not visited */ s[u] = true; for(vector< ii >:: iterator it = tree[u].begin(); it != tree[u].end(); it ++) { if(!s[(*it).first]) { dfs_lca((*it).first, l + 1); E.pb(u); L.pb(l); } } } s[u] = false; } /* for RMQ */ int M[100010][20]; inline int nlz(unsigned x) { int n; if (x == 0) return(32); n = 0; if (x <= 0x0000FFFF) {n = n +16; x = x <<16;} if (x <= 0x00FFFFFF) {n = n + 8; x = x << 8;} if (x <= 0x0FFFFFFF) {n = n + 4; x = x << 4;} if (x <= 0x3FFFFFFF) {n = n + 2; x = x << 2;} if (x <= 0x7FFFFFFF) {n = n + 1;} return n; } void init_rmq(vi &A) { } void rmq_prep(vi &A) { int i, j; for (i = 0; i < sz(A); i++) M[i][0] = i; for (j = 1; 1 << j <= sz(A); j++) { for (i = 0; i + (1 << j) - 1 < sz(A); i++) { if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]]) M[i][j] = M[i][j - 1]; else M[i][j] = M[i + (1 << (j - 1))][j - 1]; } } } int rmq(vi &A, int i, int j) { int k = 31 - nlz(j-i+1); if(A[ M[i][k] ] <= A[ M[j - (1<<k) + 1][k] ]) return M[i][k]; else return M[j - (1<<k) + 1][k]; } int main(void) { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else //freopen(INPUT_FILE, "r", stdin); //freopen(OUTPUT_FILE, "w", stdout); #endif int n; int m; cin >> n; buildTree(n); FOR(i,n-1) { int u,v,w; cin >> u >> v >> w; addEdge(u,v,w); } assignRoot(0); dfs(treeRoot, 0); init_lca(n); dfs_lca(treeRoot, 0); rmq_prep(L); cin >> m; FOR(i,m) { int u,v,p; cin >> u >> v; p = E[ rmq(L, min(R[u], R[v]), max(R[u], R[v])) ]; cout << c[u] + c[v] - 2*c[p] << endl; } return 0; }
page revision: 0, last edited: 12 May 2007 20:39