#include <bits/stdc++.h>
#define N 30005
#define K 20
#define M 15
using namespace std;
vector<int> adj[N];
int par[N][M];
int dep[N];
int timer = 1;
int tin[N],tout[N];
int cnt[N][K+1][K];
struct BIT{
vector<int> bit;
int n;
BIT(){
n = N;
bit.assign(n,0);
}
void upd(int pos,int val){
for(;pos < n;pos += pos & -pos){
bit[pos] += val;
}
}
int get(int pos){
int ret = 0;
for(;pos > 0;pos -= pos & -pos){
ret += bit[pos];
}
return ret;
}
void upd(int l,int r,int val){
upd(l,val);
upd(r+1,-val);
}
}bt[K+1][K];
void dfs(int v,int pr){
tin[v] = timer++;
dep[v] = dep[pr] + 1;
par[v][0] = pr;
for(auto u:adj[v]){
if(u == pr)continue;
dfs(u,v);
}
tout[v] = timer-1;
}
vector<int> get_path(int u,int v){
vector<int> v1,v2;
v1.push_back(u);
while(tin[v] < tin[u] || tout[u] < tin[v]){
u = par[u][0];
v1.push_back(u);
}
while(v != u){
v2.push_back(v);
v = par[v][0];
}
reverse(v2.begin(),v2.end());
for(auto c:v2){
v1.push_back(c);
}
return v1;
}
int lca(int a,int b){
if(dep[a] < dep[b])
swap(a,b);
for(int i = M-1;i>=0;i--){
if(dep[par[a][i]] >= dep[b]){
a = par[a][i];
}
}
if(a == b)
return a;
for(int i =M-1;i>=0;i--){
if(par[a][i] != par[b][i]){
a = par[a][i];
b = par[b][i];
}
}
return par[a][0];
}
void trafficker(int u,int v,int val){
auto path = get_path(u,v);
int sz = path.size();
for(int i = 0;i<sz;i++){
cnt[path[i]][sz][i] += val;
bt[sz][i].upd(tin[path[i]],tout[path[i]],val);
}
}
long long get(int a,int t){
long long ret = 0;
for(int i = 1;i<=K;i++){
for(int j = 0;j<i;j++){
long long time = (t + 1) / i + (j < (t+1)%i);
ret += (time) * bt[i][j].get(tin[a]);
}
}
return ret;
}
long long get2(int a,int t){
long long ret = 0;
for(int i = 1;i<=K;i++){
for(int j = 0;j<i;j++){
long long time = (t + 1) / i + (j < (t+1)%i);
ret += (time) * cnt[a][i][j];
}
}
return ret;
}
long long get(int u,int v,int t){
if(t == -1)return 0;
int lc = lca(u,v);
long long ret = get(u,t) + get(v,t) - 2*get(lc,t) + get2(lc,t);
// long long ret = 0;
// for(auto x:get_path(u,v)){
// ret += get2(x,t);
// }
return ret;
}
void solve(){
int n;
cin >> n;
for(int i = 1;i<n;i++){
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1,0);
for(int j = 1;j<M;j++){
for(int i = 1;i<=n;i++){
par[i][j] = par[par[i][j-1]][j-1];
}
}
int k;
cin >> k;
for(int i = 1;i<=k;i++){
int u,v;
cin >> u >> v;
trafficker(u,v,1);
}
int q;
cin >> q;
while(q--){
int type;
cin >> type;
if(type < 3){
int u,v;
cin >> u >> v;
trafficker(u,v,(type == 1?1:-1));
}
if(type == 3){
int u,v,t1,t2;
cin >> u >> v >> t1 >> t2;
cout << get(u,v,t2) - get(u,v,t1-1) << endl;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while(t--){
solve();
}
#ifdef Local
cout << endl <<fixed << setprecision(2) << 1000.0 * clock() /CLOCKS_PER_SEC << " milliseconds." << endl;
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
50388 KB |
Output is correct |
| 2 |
Correct |
25 ms |
52152 KB |
Output is correct |
| 3 |
Correct |
28 ms |
52000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
67756 KB |
Output is correct |
| 2 |
Correct |
125 ms |
66048 KB |
Output is correct |
| 3 |
Correct |
136 ms |
67416 KB |
Output is correct |
| 4 |
Correct |
120 ms |
67816 KB |
Output is correct |
| 5 |
Correct |
126 ms |
67556 KB |
Output is correct |
| 6 |
Correct |
138 ms |
67752 KB |
Output is correct |
| 7 |
Correct |
125 ms |
67392 KB |
Output is correct |
| 8 |
Correct |
118 ms |
68092 KB |
Output is correct |
| 9 |
Correct |
117 ms |
68212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1461 ms |
103600 KB |
Output is correct |
| 2 |
Correct |
1513 ms |
104168 KB |
Output is correct |
| 3 |
Correct |
1487 ms |
103800 KB |
Output is correct |
| 4 |
Correct |
1360 ms |
103432 KB |
Output is correct |
| 5 |
Correct |
1541 ms |
103060 KB |
Output is correct |
| 6 |
Correct |
1541 ms |
104460 KB |
Output is correct |
| 7 |
Correct |
1318 ms |
104208 KB |
Output is correct |
| 8 |
Correct |
1539 ms |
104192 KB |
Output is correct |
