#include <bits/stdc++.h>
using namespace std;
int n, k;
int tin[30005], tout[30005], anc[30005][23], mat[23][23], timer, cnt;
int aint[120005][23][23], heavy[30005], head[30005], pos[30005], hei[30005], siz[30005];
vector<int> adj[30005];
bool isanc(int u, int v)
{
return ((tin[u] <= tin[v]) && (tout[u] >= tout[v]));
}
int lca(int u, int v)
{
if(isanc(u, v)) return u;
if(isanc(v, u)) return v;
for(int i = 19; i >= 0; i--)
if(!isanc(anc[u][i], v))
u = anc[u][i];
return anc[u][0];
}
void update(int nod, int st, int dr, int poz, int val, int d1, int d2)
{
if(st == dr)
{
aint[nod][d1][d2] += val;
return;
}
int mij = (st + dr) / 2;
if(poz <= mij)
update(nod * 2, st, mij, poz, val, d1, d2);
else
update(nod * 2 + 1, mij + 1, dr, poz, val, d1, d2);
aint[nod][d1][d2] = aint[nod * 2][d1][d2] + aint[nod * 2 + 1][d1][d2];
}
int query(int nod, int st, int dr, int le, int ri, int d1, int d2)
{
if(le > ri)
return 0;
if(le == st && ri == dr)
return aint[nod][d1][d2];
int mij = (st + dr) / 2;
return query(nod * 2, st, mij, le, min(mij, ri), d1, d2) +
query(nod * 2 + 1, mij + 1, dr, max(le, mij + 1), ri, d1, d2);
}
void dfs(int nod, int p)
{
siz[nod] = 1;
anc[nod][0] = p;
for(int i = 1; i <= 19; i++)
anc[nod][i] = anc[anc[nod][i - 1]][i - 1];
timer++, tin[nod] = timer;
int maxx = -1;
for(auto it : adj[nod])
if(it != p)
{
hei[it] = hei[nod] + 1;
dfs(it, nod);
siz[nod] += siz[it];
if(siz[it] > maxx)
maxx = siz[it], heavy[nod] = it;
}
timer++, tout[nod] = timer;
}
void decompose(int nod, int h)
{
head[nod] = h, pos[nod] = ++cnt;
if(heavy[nod] != -1)
decompose(heavy[nod], h);
for(auto it : adj[nod])
if(anc[nod][0] != it && it != heavy[nod])
decompose(it, it);
}
vector<int> getpath(int a, int b, int l)
{
vector<int> ans, v2;
while(a != l)
ans.push_back(a), a = anc[a][0];
ans.push_back(l);
while(b != l)
v2.push_back(b), b = anc[b][0];
for(int i = (int)v2.size() - 1; i >= 0; i--)
ans.push_back(v2[i]);
return ans;
}
void updatepath(int a, int b, int val)
{
int l = lca(a, b);
vector<int> path = getpath(a, b, l);
int d = (int)path.size();
cnt = 0;
for(auto it : path)
{
update(1, 1, n, pos[it], val, d, cnt);
cnt++;
}
}
int calc(int a, int b, int t1, int t2)
{
for(int d = 1; d <= 20; d++)
for(int x = 0; x < d; x++)
mat[d][x] = 0;
for(; head[a] != head[b]; b = anc[head[b]][0])
{
if(hei[head[a]] > hei[head[b]])
swap(a, b);
for(int d = 1; d <= 20; d++)
for(int x = 0; x < d; x++)
mat[d][x] += query(1, 1, n, pos[head[b]], pos[b], d, x);
}
if(hei[a] > hei[b])
swap(a, b);
int rez = 0;
for(int d = 1; d <= 20; d++)
{
for(int x = 0; x < d; x++)
{
mat[d][x] += query(1, 1, n, pos[a], pos[b], d, x);
int st = t1, dr = t2;
if(d > 1)
{
while(st % d != x)
st++;
while(dr >= 0 && dr % d != x)
dr--;
if((dr < 0) || (st > dr))
continue;
}
rez += ((dr / d) - (st / d) + 1) * mat[d][x];
}
}
return rez;
}
int main()
{
for(int d = 1; d <= 20; d++)
for(int x = 0; x < 20; x++)
{
}
cin>>n;
heavy[n] = -1;
for(int i = 1; i < n; i++)
{
int a, b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
heavy[i] = -1;
}
dfs(1, 1);
decompose(1, 1);
cin>>k;
cnt = 0;
for(int i = 1; i <= k; i++)
{
int a, b;
cin>>a>>b;
updatepath(a, b, 1);
}
int q;
cin>>q;
for(int i = 1; i <= q; i++)
{
int tip, a, b;
cin>>tip>>a>>b;
if(tip == 1)
updatepath(a, b, 1);
else if(tip == 2)
updatepath(a, b, -1);
else
{
int t1, t2;
cin>>t1>>t2;
cout<<calc(a, b, t1, t2)<<'\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Correct |
17 ms |
10844 KB |
Output is correct |
| 3 |
Correct |
19 ms |
10844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
276 ms |
75100 KB |
Output isn't correct |
| 2 |
Incorrect |
335 ms |
75224 KB |
Output isn't correct |
| 3 |
Incorrect |
239 ms |
74064 KB |
Output isn't correct |
| 4 |
Incorrect |
274 ms |
75344 KB |
Output isn't correct |
| 5 |
Incorrect |
305 ms |
75104 KB |
Output isn't correct |
| 6 |
Incorrect |
285 ms |
75244 KB |
Output isn't correct |
| 7 |
Incorrect |
283 ms |
75240 KB |
Output isn't correct |
| 8 |
Incorrect |
244 ms |
75356 KB |
Output isn't correct |
| 9 |
Incorrect |
262 ms |
75512 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2907 ms |
144800 KB |
Output isn't correct |
| 2 |
Incorrect |
2628 ms |
145720 KB |
Output isn't correct |
| 3 |
Incorrect |
2741 ms |
145096 KB |
Output isn't correct |
| 4 |
Execution timed out |
3523 ms |
144068 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3523 ms |
143940 KB |
Time limit exceeded |
| 6 |
Incorrect |
2612 ms |
145828 KB |
Output isn't correct |
| 7 |
Incorrect |
2769 ms |
145984 KB |
Output isn't correct |
| 8 |
Incorrect |
2834 ms |
145832 KB |
Output isn't correct |
