#include #include #include #include #include #include #include #include #include #include #include #include #include #include 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 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 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 G[N]; vector P[N]; bool checked[N]; int number[N],first[N],last[N],D[N]; vector 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<<"おかしいよ!"<>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<>q; rep(i,q){ int k = 3; vector> X; rep(j,k){ int x;cin>>x; X.push_back({number[x], x}); } sort(all(X)); ll ans = 0; rep(j,X.size()){ int a = X[j].second; int b = X[(j+1)%X.size()].second; int p = lca(a,b); //cout<