#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
int t, n, m, k, a[300010], q, l, r;
vector<int> g[30010];
int ent[30010];
int ex[30010];
int par[30010];
int dp[30010][21][21];
int tmp=1;
bool v[30010];
void tour(int s){
v[s]=true;
for(auto u:g[s]){
if(!v[u]){
tmp++; ent[u]=tmp;
par[u]=s;
tour(u);
}
}
tmp++;
ex[s]=tmp;
v[s]=false;
}
void ins(int &u, int &v){
int l1=0, l2=0;
int cr=u;
while(!( ((ent[cr]<ent[v]) && (ex[cr]>ex[v])) ||(cr==v) ) ){
cr=par[cr]; l1++; //cout<<ent[cr]<<" "<<flush;
}
cr=v;
while(!( ((ent[cr]<ent[u]) && (ex[cr]>ex[u])) || (cr==u) ) ){
cr=par[cr]; l2++;
}
int l=(l1+l2+1);
dp[cr][l1+1][l]++;
l1=1;
cr=u;
while(!( ((ent[cr]<ent[v]) && (ex[cr]>ex[v])) ||(cr==v) ) ){
dp[cr][l1][l]++;
l1++; cr=par[cr];
}
l2=0;
cr=v;
while(!( ((ent[cr]<ent[u]) && (ex[cr]>ex[u])) ||(cr==u) ) ){
dp[cr][l-l2][l]++; l2++; cr=par[cr];
}
return;
}
void ers(int &u, int &v){
int l1=0, l2=0;
int cr=u;
while(!( ((ent[cr]<ent[v]) && (ex[cr]>ex[v])) ||(cr==v) ) ){
cr=par[cr]; l1++;
}
cr=v;
while(!( ((ent[cr]<ent[u]) && (ex[cr]>ex[u])) || (cr==u) ) ){
cr=par[cr]; l2++;
}
int l=(l1+l2+1);
dp[cr][l1+1][l]--;
l1=1;
cr=u;
while(!( ((ent[cr]<ent[v]) && (ex[cr]>ex[v])) || (cr==v) ) ){
dp[cr][l1][l]--;
l1++; cr=par[cr];
}
l2=0;
cr=v;
while(!( ((ent[cr]<ent[u]) && (ex[cr]>ex[u])) || (cr==u) ) ){
dp[cr][l-l2][l]--; l2++; cr=par[cr];
}
return;
}
int query(int &u, int &v,int t1, int t2){
int res=0;
int cr=u;
while(!( ((ent[cr]<ent[v]) && (ex[cr]>ex[v])) || (cr==v) ) ){
for(int i=1; i<=20; i++){
for(int j=1; j<=20; j++){
res+=( dp[cr][i][j]*(( ( max(((t2-i)/j), 0ll)+((t2>=i)?1ll:0ll) )-( max(((t1-1-i)/j), 0ll)+((t1>i)?1ll:0ll) ) ) ) );
}
}
cr=par[cr];
}
for(int i=1; i<=20; i++){
for(int j=1; j<=20; j++){
res+=( dp[cr][i][j]*(( ( max(((t2-i)/j), 0ll)+((t2>=i)?1ll:0ll) )-( max(((t1-1-i)/j ), 0ll)+((t1>i)?1ll:0ll) ) ) ) );
}
}
cr=v;
while(!( ((ent[cr]<ent[u]) && (ex[cr]>ex[u])) || (cr==u) ) ){
for(int i=1; i<=20; i++){
for(int j=1; j<=20; j++){
res+=( dp[cr][i][j]*(( ( max(((t2-i)/(j) ), 0ll)+((t2>=i)?1ll:0ll) )-( max(((t1-1-i)/j), 0ll)+((t1>i)?1ll:0ll) ) ) ) );
}
}
cr=par[cr];
}
return res;
}
int32_t main(){
INIT
cin>>n;
for(int i=1; i<n; i++){
int u, v; cin>>u>>v;
g[u].pb(v); g[v].pb(u);
}
ent[1]=0;
tour(1);
cin>>k;
for(int i=1; i<=k; i++){
int u, v; cin>>u>>v;
ins(u, v);
}
cin>>q;
while(q--){
int o; cin>>o;
if(o==1){
int u, v; cin>>u>>v;
ins(u, v);
}
if(o==2){
int u, v; cin>>u>>v;
ers(u, v);
}
if(o==3){
int u, v, t1, t2; cin>>u>>v>>t1>>t2;
cout<<query(u, v, t1, t2)<<"\n";
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
8 ms |
1280 KB |
Output isn't correct |
2 |
Incorrect |
1335 ms |
4768 KB |
Output isn't correct |
3 |
Incorrect |
208 ms |
4292 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3541 ms |
33400 KB |
Time limit exceeded |
2 |
Execution timed out |
3596 ms |
28792 KB |
Time limit exceeded |
3 |
Execution timed out |
3590 ms |
34076 KB |
Time limit exceeded |
4 |
Execution timed out |
3581 ms |
32760 KB |
Time limit exceeded |
5 |
Execution timed out |
3572 ms |
31100 KB |
Time limit exceeded |
6 |
Execution timed out |
3595 ms |
31640 KB |
Time limit exceeded |
7 |
Execution timed out |
3585 ms |
32252 KB |
Time limit exceeded |
8 |
Execution timed out |
3546 ms |
35832 KB |
Time limit exceeded |
9 |
Execution timed out |
3589 ms |
36224 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3528 ms |
106020 KB |
Time limit exceeded |
2 |
Execution timed out |
3608 ms |
106616 KB |
Time limit exceeded |
3 |
Execution timed out |
3608 ms |
106616 KB |
Time limit exceeded |
4 |
Execution timed out |
3604 ms |
102264 KB |
Time limit exceeded |
5 |
Execution timed out |
3590 ms |
99640 KB |
Time limit exceeded |
6 |
Execution timed out |
3594 ms |
106744 KB |
Time limit exceeded |
7 |
Execution timed out |
3600 ms |
107000 KB |
Time limit exceeded |
8 |
Execution timed out |
3606 ms |
106744 KB |
Time limit exceeded |