#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 = 16;
int sz[N];
int head[N], id[N];
int par[N], in[N];
int h[N];
int ord[2 * N];
int rmqord[LOGN ][2 * N];
int p2[2*N];
vector<int> gr[N];
void dfs_init (int nod, int dad, int &cord){
sz[nod] = 1;
par[nod] = dad;
h[nod] = h[dad] + 1;
ord[++cord] = nod;
in[nod] = cord;
for(auto x:gr[nod]){
if(x == dad)
continue;
dfs_init(x, nod, cord);
ord[++cord] = nod;
}
}
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);
}
}
int nrord;
void build_lca(){
p2[1] = 0;
for(int i = 2; i<2*N; i++)
p2[i] = 1 + p2[i/2];
for(int i =1 ; i<=nrord; i++){
rmqord[0][i] = ord[i];
}
for(int log = 1; log < LOGN; log++){
for(int i = 1; i<=nrord; i++){
int n1 = rmqord[log - 1][i];
int n2 = rmqord[log - 1][min(nrord, i + (1<<(log - 1)))];
if(h[n1] < h[n2])
rmqord[log][i] = n1;
else
rmqord[log][i] = n2;
}
}
}
int get_lca(int u, int v){
u = in[u];
v = in[v];
if(u > v)
swap(u, v);
int len = v- u + 1;
int lg = p2[len];
int n1 = rmqord[lg][u];
int n2 = rmqord[lg][v - (1<<lg) + 1];
if(h[n1] < h[n2])
return n1;
return n2;
}
int n;
void update_addway(int u, int v, int val){
int lca = get_lca(u, v);
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[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[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[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[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);
nrord = cnt;
build_lca();
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 |
78 ms |
208392 KB |
Output is correct |
| 2 |
Correct |
85 ms |
208660 KB |
Output is correct |
| 3 |
Correct |
89 ms |
208596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1832 ms |
210776 KB |
Output is correct |
| 2 |
Correct |
1414 ms |
210416 KB |
Output is correct |
| 3 |
Correct |
764 ms |
210776 KB |
Output is correct |
| 4 |
Correct |
1930 ms |
210816 KB |
Output is correct |
| 5 |
Correct |
1670 ms |
210756 KB |
Output is correct |
| 6 |
Correct |
1898 ms |
210744 KB |
Output is correct |
| 7 |
Correct |
1775 ms |
210736 KB |
Output is correct |
| 8 |
Correct |
676 ms |
210728 KB |
Output is correct |
| 9 |
Correct |
200 ms |
210756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3605 ms |
214636 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3600 ms |
215320 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3591 ms |
214916 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3575 ms |
214632 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3591 ms |
214516 KB |
Time limit exceeded |
| 6 |
Execution timed out |
3585 ms |
215436 KB |
Time limit exceeded |
| 7 |
Correct |
933 ms |
215972 KB |
Output is correct |
| 8 |
Correct |
957 ms |
215584 KB |
Output is correct |
