#include<bits/stdc++.h>
using namespace std;
const int N =30005;
const int DMAX = 21;
struct SegTree{
int rest[DMAX][DMAX];
SegTree(){
for(int i = 0; i < DMAX; i++)
for(int j = 0; j < DMAX; j++)
rest[i][j] = 0;
}
};
void update_SegTree(SegTree &a, int t, int poz, int val){
for(int i = poz; i < t; i++){
a.rest[t][i] += val;
}
}
SegTree aint[4*N];
void update(int nod, int l, int r, int poz, int mod, int rst, int val){
if(l > poz || r < poz)
return;
if(l == r){
update_SegTree(aint[nod], mod, rst, val);
return;
}
int mid = (l + r)/2;
update(2*nod, l, mid, poz, mod, rst, val);
update(2*nod + 1, mid + 1, r, poz, mod, rst, val);
update_SegTree(aint[nod], mod, rst, val);
}
long long query(int nod, int l, int r, int ql, int qr, int t){
if(r < ql || l > qr)
return 0;
if(ql <= l && r <= qr){
long long rsp = 0;
for(int i = 1; i < DMAX; i++){
int cat = t/i;
rsp += 1LL * cat * aint[nod].rest[i][i - 1];
rsp += 1LL * aint[nod].rest[i][t%i];
}
return rsp;
}
int mid = (l + r)/2;
long long lft = query(2*nod, l, mid, ql, qr, t);
long long rgt = query(2*nod + 1, mid + 1, r, ql, qr, t);
return lft + rgt;
}
/// segtree done
///hpd
const int LOGN = 15;
int sz[N];
int head[N], id[N];
int par[LOGN][N], in[N], out[N];
int h[N];
vector<int> gr[N];
void dfs_init (int nod, int dad, int &cnt){
sz[nod] = 1;
par[0][nod] = dad;
in[nod] = ++cnt;
h[nod] = h[dad] + 1;
for(auto x:gr[nod]){
if(x == dad)
continue;
dfs_init(x, nod, cnt);
}
out[nod] = cnt;
}
void dfs_buildhpd(int nod, int dad, int chead, int &idd){
head[nod] = chead;
id[nod] = ++idd;
int mson = -1;
for(auto x:gr[nod]){
if(x == dad)
continue;
if(mson == -1 || sz[x] > sz[mson])
mson = x;
}
if(mson == -1)
return;
dfs_buildhpd(mson, nod, chead, idd);
for(auto x:gr[nod]){
if(x == dad || x == mson)
continue;
dfs_buildhpd(x, nod, x, idd);
}
}
bool is_ancestor(int dad, int son){
if(in[dad] <= in[son] && out[son] <= out[dad])
return true;
return false;
}
int get_lca(int u, int v){
if(h[u] > h[v])
swap(u, v);
if(is_ancestor(u, v))
return u;
for(int pas = LOGN - 1; pas >= 0; pas--){
int most = par[pas][u];
if(most != 0 && is_ancestor(most, v) == false)
u = most;
}
if(is_ancestor(u, v))
return u;
return par[0][u];
}
int n;
void update_addway(int u, int v, int val){
int lca = u;
if(h[v] < h[u])
lca = v;
while((is_ancestor(lca, u) && is_ancestor(lca, v)) == false)
lca = par[0][lca];
int dst = h[u] - h[lca] + h[v] - h[lca] + 1;
int cnt = 0;
while(u != lca){
update(1, 1, n, id[u], dst, cnt, val);
cnt++;
u = par[0][u];
}
update(1, 1, n, id[lca], dst, cnt, val);
cnt = dst - 1;
while(v != lca){
update(1, 1, n, id[v], dst, cnt, val);
cnt--;
v = par[0][v];
}
}
long long query_chain(int u, int v, int t){
int lca = get_lca(u, v);
long long ans = 0;
while(head[u] != head[lca]){
ans += query(1, 1, n, id[head[u]], id[u], t);
u = par[0][head[u]];
}
ans += query(1, 1, n, id[lca], id[u], t);
while(head[v] != head[lca]){
ans += query(1, 1, n, id[head[v]], id[v], t);
v = par[0][head[v]];
}
if(id[lca] + 1 <= id[v])
ans+=query(1, 1, n, id[lca] + 1, id[v], t);
return ans;
}
int main()
{
// freopen(".in","r",stdin);
iostream::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i = 1; i<n; i++){
int u, v;
cin>>u>>v;
gr[u].push_back(v);
gr[v].push_back(u);
}
int cnt = 0;
dfs_init(1, 0, cnt);
for(int i = 1; i < LOGN; i++)
for(int nod = 1; nod<=n; nod++)
par[i][nod] = par[i - 1][par[i - 1][nod]];
cnt = 0;
dfs_buildhpd(1, 0, 1, cnt);
int k;
cin>>k;
for(int i = 1; i<=k; i++){
int u, v;
cin>>u>>v;
update_addway(u, v, 1);
}
int q;
cin>>q;
for(int i = 1; i<=q; i++){
int t;
cin>>t;
if(t == 1){
int u, v;
cin>>u>>v;
update_addway(u, v, 1);
}
else if(t == 2){
int u, v;
cin>>u>>v;
update_addway(u, v, -1);
}
else{
int u, v, t1, t2;
cin>>u>>v>>t1>>t2;
long long rsp = query_chain(u, v, t2);
if(t1 != 0)
rsp -= query_chain(u, v, t1 - 1);
cout<<rsp<<"\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
208196 KB |
Output is correct |
| 2 |
Correct |
86 ms |
208368 KB |
Output is correct |
| 3 |
Correct |
99 ms |
208252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1893 ms |
209572 KB |
Output is correct |
| 2 |
Correct |
1514 ms |
209516 KB |
Output is correct |
| 3 |
Correct |
768 ms |
209860 KB |
Output is correct |
| 4 |
Correct |
2021 ms |
209680 KB |
Output is correct |
| 5 |
Correct |
1675 ms |
209608 KB |
Output is correct |
| 6 |
Correct |
1883 ms |
209728 KB |
Output is correct |
| 7 |
Correct |
1745 ms |
209872 KB |
Output is correct |
| 8 |
Correct |
652 ms |
209860 KB |
Output is correct |
| 9 |
Correct |
155 ms |
209860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3600 ms |
212200 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3600 ms |
212908 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3581 ms |
212608 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3583 ms |
211952 KB |
Time limit exceeded |
| 5 |
Correct |
3471 ms |
212064 KB |
Output is correct |
| 6 |
Execution timed out |
3608 ms |
212964 KB |
Time limit exceeded |
| 7 |
Correct |
798 ms |
213484 KB |
Output is correct |
| 8 |
Correct |
814 ms |
213184 KB |
Output is correct |
