#include <stdio.h>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
//#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
const ll maxn = 1e5 + 1, maxm = 1e6 + 1;
const ll mod = 1e9 + 7, inf = 1e9, block = 550, hb = 31, base = 1000050017, biginf = 5e18;
const ld eps = 1e-9;
int n, k, q, timer;
int s[maxn], t[maxn], tin[maxn], tout[maxn], up[20][maxn];
vector<int> g[maxn];
multiset<pair<int, int>> lol[maxn];
void dfs(int v = 1, int p = 0){
up[0][v] = p;
for (int i = 1; i <= 19; ++i){
up[i][v] = up[i - 1][up[i - 1][v]];
}
tin[v] = ++timer;
for (auto to : g[v]){
if (to != p){
dfs(to, v);
}
}
tout[v] = ++timer;
}
bool upper(int a, int b){
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
vector<int> lca(int a, int b){
if (upper(b, a)){
vector<int> vec;
while (a != b){
vec.pb(a);
a = up[0][a];
}
vec.pb(a);
return vec;
}
else if (upper(a, b)){
vector<int> vec;
while (b != a){
vec.pb(b);
b = up[0][b];
}
vec.pb(b);
reverse(vec.begin(), vec.end());
return vec;
}
else{
int v = a;
for (int i = 19; i >= 0; --i){
if (up[i][v] && !upper(up[i][v], b)){
v = up[i][v];
}
}
int lc = up[0][v];
vector<int> vec;
while (a != lc){
vec.pb(a);
a = up[0][a];
}
vec.pb(lc);
vector<int> vec2;
while (b != lc){
vec2.pb(b);
b = up[0][b];
}
reverse(vec2.begin(), vec2.end());
for (auto it : vec2){
vec.pb(it);
}
return vec;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
dfs();
cin >> k;
map<pair<int, int>, vector<int>> was;
for (int i = 1; i <= k; ++i){
cin >> s[i] >> t[i];
was[mp(s[i], t[i])] = lca(s[i], t[i]);
vector<int> path = was[mp(s[i], t[i])];
int cur = 0, sz = (int)path.size();
for (auto it : path){
lol[it].insert(mp(cur, sz));
cur += 1;
}
}
cin >> q;
while (q--){
int type, u, v;
cin >> type;
cin >> u >> v;
if (type == 1){
was[mp(u, v)] = lca(u, v);
vector<int> path = was[mp(u, v)];
int cur = 0, sz = (int)path.size();
for (auto it : path){
lol[it].insert(mp(cur, sz));
cur += 1;
}
}
else if (type == 2){
vector<int> path = was[mp(u, v)];
int cur = 0, sz = (int)path.size();
for (auto it : path){
lol[it].erase(lol[it].find(mp(cur, sz)));
cur += 1;
}
}
else{
int t1, t2;
cin >> t1 >> t2;
vector<int> path = lca(u, v);
ll ans = 0;
for (auto it : path){
for (auto it2 : lol[it]){
int x = it2.f, y = it2.s;
ll k = (t1 - x) / y;
if (x + k * y < t1){
++k;
}
ll nx = x + k * y;
if (nx <= t2){
ans += 1 + (t2 - nx) / y;
}
// cout << it << " " << x << " " << y << '\n';
}
}
cout << ans << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
29 ms |
7924 KB |
Output is correct |
| 3 |
Correct |
15 ms |
7900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1137 ms |
12856 KB |
Output is correct |
| 2 |
Correct |
970 ms |
12600 KB |
Output is correct |
| 3 |
Correct |
1168 ms |
13172 KB |
Output is correct |
| 4 |
Correct |
1130 ms |
13036 KB |
Output is correct |
| 5 |
Correct |
1000 ms |
12772 KB |
Output is correct |
| 6 |
Correct |
1039 ms |
12828 KB |
Output is correct |
| 7 |
Correct |
1084 ms |
12852 KB |
Output is correct |
| 8 |
Correct |
1181 ms |
12960 KB |
Output is correct |
| 9 |
Correct |
2972 ms |
13084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3592 ms |
45432 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3584 ms |
46048 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3581 ms |
45788 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3556 ms |
45156 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3579 ms |
45048 KB |
Time limit exceeded |
| 6 |
Execution timed out |
3571 ms |
46180 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3572 ms |
46260 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3529 ms |
46108 KB |
Time limit exceeded |
