#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 = 3e4 + 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;
}
// add(i , j , d) means +d at t = x * i + j
vii tms[22][22];
void add(int u, int v, int z, int d)
{
tms[u][v].pb({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 calc(int u, int v, int t1, int t2)
{
int ret = 0;
for (int i = 1; i <= 20; ++i)
{
for (int j = 0; j < i; ++j)
{
for (auto node : tms[i][j])
{
if (!belong(u, v, node.f))
continue;
int 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 += add * node.s;
}
}
}
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
#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 |
7 ms |
1132 KB |
Output is correct |
| 2 |
Correct |
546 ms |
1388 KB |
Output is correct |
| 3 |
Correct |
614 ms |
1388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3568 ms |
3196 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3535 ms |
3392 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3537 ms |
3500 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3575 ms |
3216 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3590 ms |
3180 KB |
Time limit exceeded |
| 6 |
Execution timed out |
3589 ms |
3180 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3586 ms |
3200 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3597 ms |
3180 KB |
Time limit exceeded |
| 9 |
Execution timed out |
3581 ms |
3436 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3593 ms |
11116 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3575 ms |
11756 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3595 ms |
11500 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3599 ms |
10860 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3585 ms |
10860 KB |
Time limit exceeded |
| 6 |
Execution timed out |
3592 ms |
11628 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3600 ms |
11884 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3596 ms |
11516 KB |
Time limit exceeded |
