#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound
using ll = long long;
using ld = long double;
const int N = 6e4 + 7;
const ll mod = 1e9 + 7;
int n, t;
vi adj[N];
int up[N][18];
int st[N], en[N];
int dep[N];
inline bool upper(int u, int v) { return st[u] <= st[v] && en[u] >= en[v]; }
int lca(int u, int v)
{
if (upper(u, v))
return u;
if (upper(v, u))
return v;
for (int i = 17; ~i; --i)
{
if (!upper(up[u][i], v))
u = up[u][i];
}
return up[u][0];
}
void dfs(int x, int p)
{
st[x] = ++t;
up[x][0] = p;
dep[x] = 1 + dep[p];
for (int i = 1; i < 18; ++i)
{
up[x][i] = up[up[x][i - 1]][i - 1];
}
for (auto u : adj[x])
{
if (u != p)
{
dfs(u, x);
}
}
en[x] = ++t;
}
struct fenwick
{
int bit[2 * N];
fenwick()
{
memset(bit, 0, sizeof bit);
}
void add(int x, int v)
{
for (; x < N; x += x & -x)
bit[x] += v;
}
int upto(int x)
{
int ret = 0;
for (; x; x -= x & -x)
ret += bit[x];
return ret;
}
inline int get(int l, int r) { return upto(r) - upto(l - 1); }
} fs[21][21];
void add(int u, int v, int z, int d)
{
fs[u][v].add(st[z], d);
fs[u][v].add(en[z], -d);
}
int get(int a, int b)
{
if (upper(b, a))
swap(a, b);
assert(upper(a, b));
return dep[b] - dep[a];
}
int dist(int x, int y)
{
int lc = lca(x, y);
return get(x, lc) + get(y, lc);
}
bool belong(int x, int y, int z)
{
return dist(x, y) == dist(x, z) + dist(z, y);
}
int inside(int a, int b, int c)
{
if (a > b)
return 0;
return c >= a && c <= b;
}
int count_path(int u, int v, int i, int j)
{
int ret = 0;
int lc = lca(u, v);
ret += fs[i][j].get(st[lc], st[u]);
ret += fs[i][j].get(st[lc], st[v]);
ret -= fs[i][j].get(st[lc], st[lc]);
return ret;
}
ll calc(int u, int v, int t1, int t2)
{
ll ret = 0;
for (int i = 1; i <= 20; ++i)
{
for (int j = 0; j < i; ++j)
{
ll count = count_path(u, v, i, j);
ll add = 0;
int tb1 = t1 / i;
int tb2 = t2 / i;
if (tb1 == tb2)
{
add += inside(t1 % i, t2 % i, j);
}
else
{
add += tb2 - tb1 - 1;
add += inside(t1 % i, i - 1, j);
add += inside(0, t2 % i, j);
}
ret += 1ll * add * count;
}
}
return ret;
}
vi one_path(int u, int v)
{
vi ret = {u};
while (u != v)
{
u = up[u][0];
ret.pb(u);
}
return ret;
}
vi get_path(int u, int v)
{
int lc = lca(u, v);
if (u == lc)
{
vi ret = one_path(v, u);
reverse(all(ret));
return ret;
}
else if (v == lc)
{
return one_path(u, v);
}
else
{
vi ret = one_path(u, lc);
vi ret2 = one_path(v, lc);
ret2.pop_back();
reverse(all(ret2));
ret.insert(ret.end(), all(ret2));
return ret;
}
assert(0);
}
void Add(int u, int v, int d)
{
vi g = get_path(u, v);
for (int i = 0; i < sz(g); ++i)
add(sz(g), i, g[i], d);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
// freopen("in.in", "r", stdin);
#endif
cin >> n;
for (int i = 0; i < n - 1; ++i)
{
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
dfs(1, 1);
int k;
cin >> k;
for (int i = 0; i < k; ++i)
{
int u, v;
cin >> u >> v;
Add(u, v, 1);
}
int q;
cin >> q;
for (int i = 0; i < q; ++i)
{
int ty, u, v;
cin >> ty >> u >> v;
if (ty == 1)
{
Add(u, v, 1);
}
else if (ty == 2)
{
Add(u, v, -1);
}
else
{
int t1, t2;
cin >> t1 >> t2;
cout << calc(u, v, t1, t2) << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
209004 KB |
Output is correct |
| 2 |
Correct |
113 ms |
209004 KB |
Output is correct |
| 3 |
Correct |
114 ms |
209076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
305 ms |
210216 KB |
Output is correct |
| 2 |
Correct |
327 ms |
210156 KB |
Output is correct |
| 3 |
Correct |
256 ms |
210540 KB |
Output is correct |
| 4 |
Correct |
306 ms |
210284 KB |
Output is correct |
| 5 |
Correct |
322 ms |
210412 KB |
Output is correct |
| 6 |
Correct |
320 ms |
210412 KB |
Output is correct |
| 7 |
Correct |
318 ms |
210284 KB |
Output is correct |
| 8 |
Correct |
286 ms |
210412 KB |
Output is correct |
| 9 |
Correct |
273 ms |
210540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2536 ms |
213640 KB |
Output is correct |
| 2 |
Correct |
2371 ms |
214052 KB |
Output is correct |
| 3 |
Correct |
2327 ms |
213712 KB |
Output is correct |
| 4 |
Correct |
2820 ms |
213228 KB |
Output is correct |
| 5 |
Correct |
3144 ms |
213188 KB |
Output is correct |
| 6 |
Correct |
2339 ms |
213800 KB |
Output is correct |
| 7 |
Correct |
2280 ms |
214032 KB |
Output is correct |
| 8 |
Correct |
2288 ms |
213972 KB |
Output is correct |
