#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() 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; } const int MAX_N = 1 << 20; //葉の数 int N; //扱うデータ型をllとしている.適宜修正. ll dat[2 * MAX_N - 1]; //vectorにするのもあり ll lazy[2 * MAX_N - 1]; void init(int n_){ //簡単のため, 要素数を2のべき乗に N = 1; while(N < n_) N *= 2; //初期化処理をここに書く rep(i,2 * N - 1){ dat[i] = 0; lazy[i] = 0; } } //[a,b)にxを加算 void update(int a, int b, ll x, int now, int l, int r){ //[a,b)と[l,r)が交差しなければ, 無を返す. //評価値が最小値ならばINT_MAX. 修正すること. if(r <= a || b <= l) return; // [a, b)が[l, r)を完全に含んでいれば if(a <= l && r <= b){ lazy[now] += (x * (b-a)); }else{ //そうでなければ, 2つの個の複合値 //ここでは, 2つの子の最小値. 修正すること. dat[now] += (x * (min(b,r) - max(a,l))); update(a, b, x, now*2+1, l, (l+r)/2); update(a, b, x, now*2+2, (l+r)/2, r); } /* //葉のノード番号 k += N-1; //葉の更新処理をここに書く. dat[k] = a; //登りながら更新. while(k > 0){ k = (k-1) / 2; //中間ノードの更新処理をここに書く. dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); } */ } //[a,b)における評価値を得る. ここでは最小値としている. //nowが現在の接点番号, nowは[l, r)に対応している. //呼ぶ時は query(a,b,0,0,N) ll query(int a, int b, int now, int l, int r){ //[a,b)と[l,r)が交差しなければ, 無を返す. //評価値が最小値ならばINT_MAX. 修正すること. if(r <= a || b <= l) return 0; // [a, b)が[l, r)を完全に含んでいれば, このノードの値 if(a <= l && r <= b){ ll ret = dat[now]; ret += lazy[now]; return ret; }else{ //そうでなければ, 2つの個の複合値 //ここでは, 2つの子の最小値. 修正すること. lazy[now*2+1] += lazy[now]/2; lazy[now*2+2] += lazy[now]/2; lazy[now] = 0; ll vl = query(a, b, now*2+1, l, (l+r)/2); ll vr = query(a, b, now*2+2, (l+r)/2, r); return vl + vr; } } struct edge{ll cost; int to;}; vector G[MAX_N]; vector P[MAX_N]; bool checked[MAX_N]; int number[MAX_N],first[MAX_N],first_m[MAX_N],last[MAX_N],last_m[MAX_N],D[MAX_N]; vector tour, tour_m; int dfs(int now, int num, int depth){ D[now] = depth; checked[now] = true; number[now] = num; num++; first[now] = tour.size(); first_m[now] = tour_m.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_m.push_back(G[now][i].cost); } last[now] = tour.size() - 1; last_m[now] = tour_m.size() - 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); 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 kind;cin>>kind; if(kind == 1){ ll a,x; cin>>a>>x; update(first[a], last[a]+1, x, 0, 0, MAX_N); update(first_m[a]+skip, last_m[a]+1+skip, x, 0, 0, MAX_N); }else{ ll b; cin>>b; cout<> 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<