//Bismillahir-Rahmanir-Rahim
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define pii pair <int, int>
#define pll pair <long long, long long>
#define pld pair <ld, ld>
#define ll long long
#define ld long double
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define skip continue
#define bpop(x) (ll)__builtin_popcountll(x)
using namespace std;
const int N = 5e4 + 7;
const int M = 3e5 + 7;
const int MAXA = 1e6 + 7;
const int inf = 1e9 + 7;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ld eps = 1e-4;
pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
#define int long long
vector <pii> g[N];
bitset <4 * N> z;
int n, q, T, a[N], sz[N], d[N], p[N], heavy[N], head[N], tin[N], V[N], ord[N], t[4 * N];
void dfs(int v) {
sz[v] = 1, heavy[v] = 0;
for (auto to : g[v]) {
if (to.x == p[v])skip;
p[to.x] = v, d[to.x] = d[v] + 1;
dfs(to.x);
sz[v] += sz[to.x];
if (sz[to.x] > sz[heavy[v]])heavy[v] = to.x;
}
}
void push(int v, int tl, int tr) {
if (z[v] == 0)return;
if (tl != tr)z[v * 2] = z[v * 2 + 1] = 1;
}
void update(int v, int tl, int tr, int pos, int x) {
push(v, tl, tr);
if (tl == tr) {
t[v] += x;
//cout << pos << ' ' << pos << ':' << x << '\n';
return;
}
int mid = (tl + tr) / 2;
if (pos <= mid)update(v * 2, tl, mid, pos, x);
else update(v * 2 + 1, mid + 1, tr, pos, x);
t[v] = t[v * 2] + t[v * 2 + 1];
//cout << tl << ' ' << tr << ':' << t[v] << '\n';
}
int get(int v, int tl, int tr, int l, int r) {
push(v, tl, tr);
if (tr < l || tl > r)return 0;
if (tl >= l && tr <= r) {
int x = t[v] * (1 - z[v]);
z[v] = 1;
push(v, tl, tr);
return x;
}
int mid = (tl + tr) / 2;
return get(v * 2, tl, mid, l, r) + get(v * 2 + 1, mid + 1, tr, l, r);
}
void decompose(int v, int h) {
tin[v] = ++T, head[v] = h, ord[T] = v;
//cout << v << ':' << T << '\n';
if (heavy[v])decompose(heavy[v], h);
for (auto to : g[v]) {
if (to.x != p[v] && to.x != heavy[v])decompose(to.x, to.x);
}
}
void upd_all(int v) {
for (auto to : g[v]) {
if (to.x == p[v])skip;
update(1, 1, n, tin[to.x], to.y);
upd_all(to.x);
}
}
int hld_get(int a, int b) {
int res = 0;
while (head[a] != head[b]) {
if (d[head[a]] > d[head[b]])swap(a, b);
res += get(1, 1, n, tin[head[b]], tin[b]), b = p[head[b]];
}
if (d[a] > d[b])swap(a, b);
res += get(1, 1, n, tin[a] + 1, tin[b]);
return res;
}
void solve() {
cin >> n;
for (int i = 1;i < n;i++) {
int a, b, w;
cin >> a >> b >> w;
a++, b++;
g[a].pb({b, w}), g[b].pb({a, w});
}
dfs(1), decompose(1, 1), upd_all(1);
cin >> q;
vector <int> verts(5);
for (int i = 1;i <= q;i++) {
for (int j = 0;j < 5;j++)cin >> verts[j], verts[j]++;
z.reset();
int ans = 0;
for (int x = 0;x < 5;x++) {
for (int y = x + 1;y < 5;y++)ans += hld_get(verts[x], verts[y]);
}
cout << ans << '\n';
}
}
signed main() {
//srand(time(NULL));
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("cows.in", "r", stdin);
//freopen("cows.out", "w", stdout);
int test;
test = 1;
//cin >> test;
for (int i = 1;i <= test;i++) {
//cout << "Case " << i << ": ";
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
9316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
7764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Incorrect |
82 ms |
9316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
