結果
問題 | No.898 tri-βutree |
ユーザー |
![]() |
提出日時 | 2019-10-04 22:17:44 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 845 ms / 4,000 ms |
コード長 | 4,157 bytes |
コンパイル時間 | 1,851 ms |
コンパイル使用メモリ | 101,192 KB |
実行使用メモリ | 49,772 KB |
最終ジャッジ日時 | 2024-11-08 22:18:31 |
合計ジャッジ時間 | 15,248 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <iostream>#include <cstring>#include <algorithm>#include <vector>#include <string>#include <math.h>#include <iomanip>#include <limits>#include <list>#include <queue>#include <tuple>#include <map>#include <stack>#include <set>using namespace std;#define MOD (long long int)(1e9+7)#define ll long long int#define rep(i,n) for(int i=0; i<(int)(n); i++)#define reps(i,n) for(int i=1; i<=(int)(n); i++)#define REP(i,n) for(int i=n-1; i>=0; i--)#define REPS(i,n) for(int i=n; i>0; i--)#define INF (int)(1123456789)#define LINF (long long int)(112345678901234567)#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))#define all(v) v.begin(), v.end()const int N = (int)3e5;ll mpow(ll a, ll b){if(b==0) return 1;else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}else return mpow(a,b-1) * a % MOD;}ll lpow(ll a, ll b){if(b==0) return 1;else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}else return lpow(a,b-1) * a;}ll gcd(ll a, ll b){if(b==0) return a;else return gcd(b, a%b);}vector<ll> kaijo_memo;ll kaijo(ll n){if(kaijo_memo.size() > n) return kaijo_memo[n];if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);return kaijo_memo[n];}vector<ll> gyaku_kaijo_memo;ll gyaku_kaijo(ll n){if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n];if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1);while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) %MOD);return gyaku_kaijo_memo[n];}ll nCr(ll n, ll r){if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く?不安.if(n < r || r < 0) return 0;ll ret = 1;ret *= kaijo(n); ret %= MOD;ret *= gyaku_kaijo(r); ret %= MOD;ret *= gyaku_kaijo(n-r); ret %= MOD;return ret;}struct edge{ll cost; int to;};vector<edge> G[N];vector<int> P[N];bool checked[N];int number[N],first[N],last[N],D[N];vector<ll> tour;int dfs(int now, int num, int depth){D[now] = depth;checked[now] = true;number[now] = num;num++;first[now] = tour.size();rep(i,G[now].size()){int next = G[now][i].to;if(checked[next]) continue;tour.push_back(G[now][i].cost);P[next].push_back(now);int ret = dfs(next, num, depth+1);if(ret == -1) continue;num = ret;tour.push_back(G[now][i].cost * -1);}return num;}int lca(int a, int b){REP(t,30){if(D[a] - lpow(2,t) >= D[b]){a = P[a][t];}else if(D[b] - lpow(2,t) >= D[a]){b = P[b][t];}}REP(t,30){if(P[a][t] != P[b][t]){a = P[a][t];b = P[b][t];}}if(a != b){a = P[a][0];b = P[b][0];}if(a != b){cout<<"おかしいよ!"<<endl;while(true){}}return a;}int main(void){int n;cin>>n;rep(i,n-1){int u,v,w;cin>>u>>v>>w;G[u].push_back({w,v});G[v].push_back({w,u});}rep(i,n){checked[i] = false;}P[0].push_back(-1);tour.push_back(0);dfs(0, 0, 0);rep(t,30){rep(i,n){if(P[i][t] == -1){P[i].push_back(-1);continue;}P[i].push_back(P[P[i][t]][t]);}}/*rep(i,n){cout<<number[i]<<" ";}cout<<endl;rep(i,tour.size()){cout<<tour[i]<<" ";}cout<<endl;rep(i,n){cout<<P[i][1]<<" ";}cout<<endl;*/rep(i,tour.size()-1){tour[i+1] += tour[i];}int q;cin>>q;rep(i,q){int k = 3;vector<pair<ll,ll>> X;rep(j,k){ll x;cin>>x;X.push_back({number[x], x});}sort(all(X));ll ans = 0;rep(j,X.size()){ll a = X[j].second;ll b = X[(j+1)%X.size()].second;ll p = lca(a,b);//cout<<a<<" "<<b<<" "<<p<<" "<<tour[first[b]-1] - tour[first[p]-1] + tour[first[a]-1] - tour[first[p]-1]<<endl;ans += tour[first[b]-1] - tour[first[p]-1] + tour[first[a]-1] - tour[first[p]-1];}cout<<ans/2<<endl;}return 0;}