//Bismillahir-Rahmanir-Rahim
# include <bits/stdc++.h>
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x << " = " << x << endl;
# define pll pair <ll, ll>
# define pii pair <int, int>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll maxn = 5e4 + 2;
const ll inf = 2e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
const ll P = 67;
using namespace std;
int n, q, timer;
vector <pii> g[maxn];
int uu[maxn], vv[maxn], ww[maxn];
int tin[maxn], d[maxn];
int sz[maxn], mx[maxn];
int par[maxn], st[maxn];
ll pref[maxn];
void dfs (int v = 1, int pa = 1)
{
sz[v] = 1, mx[v] = -1;
for (pii it : g[v])
{
int to = it.ff, w = it.ss;
if (to == pa) continue;
dfs(to, v);
sz[v] += sz[to];
if (mx[v] == -1 || sz[mx[v]] < sz[to])
mx[v] = to;
}
}
void hld (int v = 1, int pa = 1)
{
tin[v] = ++timer;
par[v] = pa;
d[v] = d[pa] + 1;
if (mx[v] != -1)
{
st[mx[v]] = st[v];
hld(mx[v], v);
}
for (pii it : g[v])
{
int to = it.ff, w = it.ss;
if (to == pa || to == mx[v]) continue;
st[to] = to;
hld(to, v);
}
}
struct segtree
{
int t[maxn * 4], z[maxn * 4];
void build (int v = 1, int tl = 1, int tr = n)
{
t[v] = 0, z[v] = -1;
if (tl == tr)
{
return;
}
int tm = (tl + tr) >> 1;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
}
void push (int v, int tl, int tr)
{
if (z[v] != -1 && tl != tr)
{
t[v * 2] = t[v * 2 + 1] = z[v];
z[v * 2] = z[v * 2 + 1] = z[v];
}
}
void update (int l, int r, int x, int v = 1, int tl = 1, int tr = n)
{
push(v, tl, tr);
if (tr < l || r < tl) return;
if (l <= tl && tr <= r)
{
t[v] = x;
z[v] = x;
return;
}
int tm = (tl + tr) >> 1;
update(l, r, x, v * 2, tl, tm);
update(l, r, x, v * 2 + 1, tm + 1, tr);
t[v] = (t[v * 2] && t[v * 2 + 1]);
}
int get (int v = 1, int tl = 1, int tr = n)
{
push(v, tl, tr);
if (t[v])
{
return pref[tr] - pref[tl - 1];
}
if (tl == tr) return 0;
int tm = (tl + tr) >> 1;
return get(v * 2, tl, tm) + get(v * 2 + 1, tm + 1, tr);
}
} t;
int lca (int u, int v)
{
while (1)
{
int x = st[u], y = st[v];
if (x == y)
{
if (tin[u] < tin[v])
{
return u;
}
else
{
return v;
}
}
else if (d[x] >= d[y])
{
u = par[x];
}
else
{
v = par[y];
}
}
return -1;
}
void upd (int u, int v)
{
while (1)
{
int x = st[u], y = st[v];
if (x == y)
{
int l = min(tin[u], tin[v]);
int r = max(tin[u], tin[v]);
t.update(l + 1, r, 1);
break;
}
if (d[x] >= d[y])
{
int l = min(tin[u], tin[x]);
int r = max(tin[u], tin[x]);
t.update(l, r, 1);
u = par[x];
}
else
{
int l = min(tin[y], tin[v]);
int r = max(tin[y], tin[v]);
t.update(l, r, 1);
v = par[y];
}
}
}
void ma1n (/* SABR */)
{
cin >> n;
for (int i = 1; i < n; ++i)
{
cin >> uu[i] >> vv[i] >> ww[i];
uu[i]++, vv[i]++;
g[uu[i]].pb({vv[i], ww[i]});
g[vv[i]].pb({uu[i], ww[i]});
}
dfs ();
st[1] = 1;
hld ();
for (int i = 1; i < n; ++i)
{
if (uu[i] == par[vv[i]])
{
pref[tin[vv[i]]] += ww[i];
}
else
{
pref[tin[uu[i]]] += ww[i];
}
}
for (int i = 1; i <= n; ++i)
{
pref[i] += pref[i - 1];
}
cin >> q;
while (q--)
{
vector <int> x(5);
t.build();
for (int &a : x)
{
cin >> a;
a++;
}
int lc = lca(x[0], x[1]);
for (int i = 2; i < 5; ++i)
{
lc = lca(lc, x[i]);
}
for (int i = 0; i < 5; ++i)
{
upd(x[i], lc);
}
int res = t.get();
cout << res << endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
int ttt = 1;
// cin >> ttt;
for (int test = 1; test <= ttt; ++test)
{
// cout << "Case " << test << ":" << '\n';
ma1n();
}
return 0;
}
// 998batrr | BbIWEJI 3A TObOU!!!
// tourist | BbIWEJI 3A TObOU!!!
Compilation message
roadsideadverts.cpp: In function 'void dfs(int, int)':
roadsideadverts.cpp:40:25: warning: unused variable 'w' [-Wunused-variable]
40 | int to = it.ff, w = it.ss;
| ^
roadsideadverts.cpp: In function 'void hld(int, int)':
roadsideadverts.cpp:61:25: warning: unused variable 'w' [-Wunused-variable]
61 | int to = it.ff, w = it.ss;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1068 ms |
8468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
45 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
39 ms |
9428 KB |
Output is correct |
| 3 |
Correct |
39 ms |
9504 KB |
Output is correct |
| 4 |
Correct |
40 ms |
9528 KB |
Output is correct |
| 5 |
Correct |
40 ms |
9468 KB |
Output is correct |
| 6 |
Correct |
40 ms |
9428 KB |
Output is correct |
| 7 |
Correct |
51 ms |
9420 KB |
Output is correct |
| 8 |
Correct |
42 ms |
9496 KB |
Output is correct |
| 9 |
Correct |
39 ms |
9428 KB |
Output is correct |
| 10 |
Correct |
39 ms |
9452 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Execution timed out |
1068 ms |
8468 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
