#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const int N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7 ;
int P[N] , D[N] , H[N] , B[N] , pos[N];
vector<int> g[N];
int a[N] , b[N] , d[N] , c[N] , NW , t[N*4] , u[N*4] , timer;
int up[N][20] , n , sz[N];
void upd(int v, int tl, int tr , int pos , int val){
if(tl == tr){
t[v] = val;
return;
}
int tm = (tl+tr) >> 1;
if(tm >= pos) upd(v*2,tl,tm,pos,val);
else upd(v*2+1,tm+1,tr,pos,val);
t[v] = t[v*2]+t[v*2+1];
}
int lca(int a , int b){
if(D[a] > D[b]) swap(a,b);
for(int i = 19; i >= 0; i--){
if(D[a] <= D[up[b][i]]){
b = up[b][i];
}
}
if(a == b) return a;
for(int i = 19; i >= 0; i--){
if(up[a][i] != up[b][i]){
b = up[b][i];
a = up[a][i];
}
}
a = up[a][0];
return a;
}
void dfs(int v , int pr){
P[v] = pr;
D[v] = D[pr]+1;
int mx = 0;
sz[v] = 1;
up[v][0] = pr;
for(int i = 1; i < 20; i++) up[v][i] = up[up[v][i-1]][i-1];
for(int i : g[v]){
int to = (v^a[i]^b[i]);
if(to == pr) continue;
d[to] = c[i];
dfs(to,v);
sz[v] += sz[to];
if(sz[to] > mx){
mx = sz[to];
H[v] = to;
}
}
}
void decompose(int v ,int h){
B[v] = h;
pos[v] = ++NW;
if(H[v]) decompose(H[v],h);
for(int i : g[v]){
int to = (v^a[i]^b[i]);
if(to != P[v] && to != H[v]) decompose(to,to);
}
}
int getsum(int v ,int tl , int tr , int l , int r , int mx){
int resmx = max(mx,u[v]);
if(l <= tl && tr <= r){
u[v] = timer;
if(resmx != timer) return t[v];
else return 0;
}
if(tl > r || tr < l) return 0;
int tm = (tl+tr) >> 1;
return getsum(v*2,tl,tm,l,r,resmx) + getsum(v*2+1,tm+1,tr,l,r,resmx);
}
int get(int a , int b){
int res = 0;
for(; B[a] != B[b]; a = P[B[a]]){
res += getsum(1,1,n,pos[B[a]],pos[a],0);
}
res += getsum(1,1,n,pos[b]+1,pos[a],0);
return res;
}
void solve(){
cin >> n;
for(int i = 1; i < n;i++){
cin >> a[i] >> b[i] >> c[i];
a[i]++;
b[i]++;
g[a[i]].push_back(i);
g[b[i]].push_back(i);
}
dfs(1,0);
decompose(1,1);
for(int i = 1; i <= n; i++) upd(1,1,n,pos[i],d[i]);
int q;
cin >> q;
for(int i = 1; i <= q; i++){
int a , b , c , d, e;
cin >> a >> b >> c >> d >> e;
timer++;
a++;
b++;
c++;
d++;
e++;
int LCA = lca(a,b);
LCA = lca(LCA,c);
LCA = lca(LCA,d);
LCA = lca(LCA,e);
ll ans = get(a,LCA);
ans += get(b,LCA);
ans += get(c,LCA);
ans += get(d,LCA);
ans += get(e,LCA);
cout << ans << "\n";
}
}
/*
*/
signed main(){
ios;
solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
60 ms |
16020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
33 ms |
13544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Incorrect |
60 ms |
16020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
