結果
問題 | No.898 tri-βutree |
ユーザー |
|
提出日時 | 2019-10-04 22:07:42 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 522 ms / 4,000 ms |
コード長 | 4,637 bytes |
コンパイル時間 | 2,573 ms |
コンパイル使用メモリ | 167,668 KB |
実行使用メモリ | 31,488 KB |
最終ジャッジ日時 | 2024-11-08 22:13:42 |
合計ジャッジ時間 | 12,333 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
/*** author: yuji9511 ***/#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<ll,ll> lpair;const ll MOD = 1e9+7;const ll INF = 1e18;#define rep(i,m,n) for(ll i=(m);i<(n);i++)#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};void print() {}template <class H,class... T>void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}vector<lpair> tree[100010];ll parent[100010] = {};ll depth[100010] = {};ll next_val[25][100010] = {};ll logN = 0;ll sum[100010] = {};void dfs2(ll cur, ll par, ll d){if(par != -1) sum[cur] = sum[par] + d;for(auto &e: tree[cur]){if(e.first == par) continue;dfs2(e.first, cur, e.second);}}void dfs(ll cur, ll par, ll d){depth[cur] = d;parent[cur] = par;for(auto &e: tree[cur]){if(e.first == par) continue;dfs(e.first, cur, d+1);}}ll get_parent(ll cur, ll num) {ll p = cur;rrep(k,logN-1, 0){if(p == -1){break;}if((num >> k) & 1){p = next_val[k][p];}}return p;}int main(){cin.tie(0);ios::sync_with_stdio(false);ll N;cin >> N;rep(i,0,N-1){ll u,v,w;cin >> u >> v >> w;tree[u].push_back({v,w});tree[v].push_back({u,w});}logN = floor(log2(N)) + 1;dfs(0, -1, 0);rep(i,0,N){next_val[0][i] = parent[i];}rep(k,0,logN){rep(i,0,N){if(next_val[k][i] == -1){next_val[k+1][i] = -1;}else{next_val[k+1][i] = next_val[k][next_val[k][i]];}}}dfs2(0,-1,0);ll Q;cin >> Q;while(Q--){ll x,y,z;cin >> x >> y >> z;ll ans = sum[x] + sum[y] + sum[z];ll va = x, vb = y;if(depth[va] > depth[vb]){va = get_parent(va, depth[va] - depth[vb]);}else if(depth[va] < depth[vb]){vb = get_parent(vb, depth[vb] - depth[va]);}ll lv = -1, rv = N+1;while(rv - lv > 1){ll mid = (rv + lv) / 2;ll ta = get_parent(va, mid);ll tb = get_parent(vb, mid);if(ta == -1 || tb == -1){rv = mid;}else if(ta != tb){lv = mid;}else{rv = mid;}}ll pos = get_parent(va, rv);ans -= sum[pos];va = y; vb = z;if(depth[va] > depth[vb]){va = get_parent(va, depth[va] - depth[vb]);}else if(depth[va] < depth[vb]){vb = get_parent(vb, depth[vb] - depth[va]);}lv = -1; rv = N+1;while(rv - lv > 1){ll mid = (rv + lv) / 2;ll ta = get_parent(va, mid);ll tb = get_parent(vb, mid);if(ta == -1 || tb == -1){rv = mid;}else if(ta != tb){lv = mid;}else{rv = mid;}}pos = get_parent(va, rv);ans -= sum[pos];va = z; vb = x;if(depth[va] > depth[vb]){va = get_parent(va, depth[va] - depth[vb]);}else if(depth[va] < depth[vb]){vb = get_parent(vb, depth[vb] - depth[va]);}lv = -1; rv = N+1;while(rv - lv > 1){ll mid = (rv + lv) / 2;ll ta = get_parent(va, mid);ll tb = get_parent(vb, mid);if(ta == -1 || tb == -1){rv = mid;}else if(ta != tb){lv = mid;}else{rv = mid;}}pos = get_parent(va, rv);ans -= sum[pos];print(ans);// ll vx = x, vy = y, vz = z;// ll dmin = min({depth[x], depth[y], depth[z]});// if(dmin == depth[x]){// vy = get_parent(vy, depth[y] - depth[x]);// vz = get_parent(vz, depth[z] - depth[x]);// }else if(dmin == depth[y]){// vx = get_parent(vx, depth[x] - depth[y]);// vz = get_parent(vz, depth[z] - depth[y]);// }else{// vx = get_parent(vx, depth[x] - depth[z]);// vy = get_parent(vy, depth[y] - depth[z]);// }// ll lv = -1, rv = N+1;// while(rv - lv > 1){// ll mid = (rv + lv) / 2;// ll tx = get_parent(vx, mid);// ll ty = get_parent(vy, mid);// ll tz = get_parent(vz, mid);// if(tx == -1 || ty == -1 || tz == -1){// rv = mid;// }else if(tx != ty || ty != tz || tz != tx){// lv = mid;// }else{// rv = mid;// }// }// ll pos = get_parent(vx, rv);// print(pos);}}