Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //In the name of ALLAH
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef vector<ll> vl;
- typedef vector<vi> vvi;
- typedef vector<vl> vvl;
- typedef pair<int,int> pii;
- typedef pair<double, double> pdd;
- typedef pair<ll, ll> pll;
- typedef vector<pii> vii;
- typedef vector<pll> vll;
- typedef double dl;
- #define PB push_back
- //#define PB emplace_back
- #define F first
- #define S second
- #define MP make_pair
- #define endl '\n'
- #define all(a) (a).begin(),(a).end()
- #define sz(x) (int)x.size()
- #define mid(l,r) ((r+l)/2)
- #define left(node) (node*2)
- #define right(node) (node*2+1)
- #define mx_int_prime 999999937
- const double PI = acos(-1);
- const double eps = 1e-9;
- const int inf = 2000000000;
- const ll infLL = 9000000000000000000;
- #define MOD 1000000007
- //#define harmonic(n) 0.57721566490153286l+log(n)
- #define mem(a,b) memset(a, b, sizeof(a) )
- #define gcd(a,b) __gcd(a,b)
- #define sqr(a) ((a) * (a))
- #define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- #define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
- #define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
- typedef vector<int>::iterator vit;
- typedef set<int>::iterator sit;
- inline bool checkBit(ll n, int i) { return n&(1LL<<i); }
- inline ll setBit(ll n, int i) { return n|(1LL<<i); }
- inline ll resetBit(ll n, int i) { return n&(~(1LL<<i)); }
- struct edge {
- int u, v, w;
- };
- bool cmp ( const edge &a, const edge &b )
- {
- return a.w < b.w;
- }
- string to_s(int t)
- {
- stringstream ss;
- ss << t;
- return ss.str();
- }
- int dx[] = {0, 0, +1, -1};
- int dy[] = {+1, -1, 0, 0};
- //int dx[] = {+1, 0, -1, 0, +1, +1, -1, -1};
- //int dy[] = {0, +1, 0, -1, +1, -1, +1, -1};
- inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
- inline bool isLeapYear(ll year) { return (year%400==0) || (year%4==0 && year%100!=0); }
- inline ll lcm ( ll a, ll b ) { return ( a * ( b / gcd (a, b) ) ); }
- inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
- inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
- inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
- inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
- inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
- inline ll modInverse(ll a) { return modPow(a, MOD-2); }
- inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
- /*
- bool seive[1010000];
- vi prime;
- void seiveGen(int limit) {
- limit += 100;
- int sqrtn = sqrt(limit);
- for(int i = 3; i <= sqrtn; i += 2) {
- if(!seive[i>>1]) {
- for(int j = i * i; j < limit; j += i + i) {
- seive[j>>1] = 1;
- }
- }
- }
- prime.PB(2);
- for(int i = 3; i < limit; i += 2) {
- if(!seive[i>>1]) prime.PB(i);
- }
- }
- */
- //
- //debug
- //#ifdef
- template < typename F, typename S >
- ostream& operator << ( ostream& os, const pair< F, S > & p ) {
- return os << "(" << p.first << ", " << p.second << ")";
- }
- template < typename T >
- ostream &operator << ( ostream & os, const vector< T > &v ) {
- os << "{";
- for(auto it = v.begin(); it != v.end(); ++it) {
- if( it != v.begin() ) os << ", ";
- os << *it;
- }
- return os << "}";
- }
- template < typename T >
- ostream &operator << ( ostream & os, const set< T > &v ) {
- os << "[";
- for(auto it = v.begin(); it != v.end(); ++it) {
- if( it != v.begin() ) os << ", ";
- os << *it;
- }
- return os << "]";
- }
- template < typename T >
- ostream &operator << ( ostream & os, const multiset< T > &v ) {
- os << "[";
- for(auto it = v.begin(); it != v.end(); ++it) {
- if( it != v.begin() ) os << ", ";
- os << *it;
- }
- return os << "]";
- }
- template < typename F, typename S >
- ostream &operator << ( ostream & os, const map< F, S > &v ) {
- os << "[";
- for(auto it = v.begin(); it != v.end(); ++it) {
- if( it != v.begin() ) os << ", ";
- os << it -> first << " = " << it -> second ;
- }
- return os << "]";
- }
- #define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
- clock_t tStart = clock();
- #define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
- void faltu () {
- cerr << endl;
- }
- template <typename T>
- void faltu( T a[], int n ) {
- for(int i = 0; i < n; ++i) cerr << a[i] << ' ';
- cerr << endl;
- }
- template <typename T, typename ... hello>
- void faltu( T arg, const hello &... rest) {
- cerr << arg << ' ';
- faltu(rest...);
- }
- //#else
- //#define dbg(args...)
- const int mx = 1e5+123;
- int p[mx][30], p_mx[mx][30], chainHead[mx], chainInd[mx], chainNo, ptr, basePos[mx],baseArry[mx], parent[mx], level[mx], n, sz[mx];
- vii Aj[mx];
- int dfs ( int u, int lev )
- {
- level[u] = lev;
- sz[u] = 1;
- for ( auto v : Aj[u] ) {
- if ( parent[u] != v.F ) {
- parent[v.F] = u;
- sz[u] += dfs ( v.F, lev+1 );
- }
- }
- return sz[u];
- }
- void preprocess()
- {
- for ( int i = 1; i <= n; i++ ) {
- p[i][0] = parent[i];
- p_mx[i][0] = baseArry[i];
- }
- for ( int j = 1; ( 1 << j ) <= n; j++ ) {
- for ( int i = 1; i <= n; i++ ) {
- if ( p[i][j-1] != -1 ) p[i][j] = p[p[i][j-1]][j-1];
- if ( i+(1<<(j-1)) <= n ) p_mx[i][j] = max ( p_mx[i][j-1], p_mx[i+(1<<(j-1))][j-1] );
- }
- }
- }
- int query_mx ( int l, int r )
- {
- int j = log2 ( r - l + 1 );
- return max ( p_mx[l][j], p_mx[r-(1<<j)+1][j] );
- }
- int LCA ( int u, int v )
- {
- if ( level[u] < level[v] ) swap ( u, v );
- int dist = level[u] - level[v];
- while ( dist > 0 ) {
- int rise = log2 ( dist );
- u = p[u][rise];
- dist -= ( 1 << rise );
- }
- if ( u == v ) return u;
- for ( int i = 20; i >= 0; i-- ) {
- if ( p[u][i] != p[v][i] && p[u][i] != -1 ) {
- u = p[u][i];
- v = p[v][i];
- }
- }
- return parent[u];
- }
- void HLD ( int u, int cost )
- {
- if ( chainHead[chainNo] == -1 ) {
- chainHead[chainNo] = u;
- }
- chainInd[u] = chainNo;
- basePos[u] = ++ptr;
- baseArry[ptr] = cost;
- int m = -1, id = -1, c = -1;
- for ( auto v : Aj[u] ) {
- if ( sz[v.F] > m && v.F != parent[u] ) {
- m = sz[v.F], id = v.F, c = v.S;
- }
- }
- if ( id != -1 ) HLD ( id, c );
- for ( auto v : Aj[u] ) {
- if ( parent[u] != v.F && v.F != id ) {
- chainNo++;
- HLD ( v.F, v.S );
- }
- }
- }
- int query_up ( int u, int v )
- {
- int chainU, chainV = chainInd[v], ans = 0;
- if ( v == u ) return 0;
- while ( 1 ) {
- chainU = chainInd[u];
- if ( chainU == chainV ) {
- if ( u == v ) return ans;
- ans = max ( ans, query_mx( basePos[v]+1, basePos[u] ) );
- return ans;
- }
- ans = max ( ans, query_mx( basePos[chainHead[chainU]], basePos[u] ) );
- u = chainHead[chainU];
- u = parent[u];
- }
- }
- int query ( int u, int v )
- {
- int lca = LCA ( u, v );
- return max ( query_up( u, lca ), query_up( v, lca ) );
- }
- int main()
- {
- optimize();
- int t, u, v, w;
- while ( cin >> n ) {
- if ( n == 0 ) break;
- mem ( chainHead, -1 );
- mem ( p, -1 );
- ptr = 0, chainNo = 1;
- for ( int i = 0; i <= 1e5; i++ ) {
- Aj[i].clear();
- parent[i] = i;
- }
- for ( int i = 1; i < n; i++ ) {
- cin >> u >> v >> w;
- Aj[u].PB ( { v, w } );
- Aj[v].PB ( { u, w } );
- }
- dfs ( 1, 0 );
- HLD ( 1, -1 );
- preprocess();
- int q;
- cin >> q;
- while ( q-- ) {
- cin >> u >> v;
- cout << query( u, v ) << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement