QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#466926 | #1163. Another Tree Queries Problem | yinhee | WA | 110ms | 12136kb | C++14 | 5.0kb | 2024-07-08 11:55:22 | 2024-07-08 11:55:25 |
Judging History
answer
// Problem: A. Another Tree Queries Problem
// Contest: Codeforces - 2020-2021 Winter Petrozavodsk Camp, Day 9 Contest (XXI Open Cup, Grand Prix of Suwon)
// URL: https://codeforces.com/gym/102979/problem/A
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define mems(x,y) memset(x,y,sizeof x)
#define Mp make_pair
#define eb emplace_back
#define gc getchar
#define pc putchar
#define fi first
#define se second
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,a,b) for(int i=(a);i>=(b);i--)
#define go(i,u) for(int i=head[u];i;i=e[i].nxt)
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>
il void read(T &x){
int f=1;x=0;char c=gc();
while(c<'0'||c>'9'){
if(c=='-'){
f=-1;
}
c=gc();
}
while(c>='0'&&c<='9'){
x=x*10+c-48,c=gc();
}
x*=f;
}
template<typename T,typename ...Args>
void read(T &x,Args &...args){
read(x),read(args...);
}
template<typename T>
il void write(T x){
char buf[43];int len=0;
if(x<0){
pc('-'),x=-x;
}
do{
buf[++len]=x%10,x/=10;
}while(x);
while(len){
pc(buf[len--]+'0');
}
}
}
using namespace my_std;
const int N=2e5+7,M=-1,inf=0x3f3f3f3f,mod=0;
int n,m;
int dep[N],siz[N],son[N],fa[N][23];
int cur,dfn[N],rk[N],top[N];
int tot,head[N];
struct node{
int to,nxt;
}e[N<<1];
il void add(int u,int v){
e[++tot]={v,head[u]},head[u]=tot;
}
void dfs1(int u,int f){
siz[u]=1;
fa[u][0]=f,dep[u]=dep[f]+1;
rep(i,1,18){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
go(i,u){
int v=e[i].to;
if(v==f){
continue;
}
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]){
son[u]=v;
}
}
}
void dfs2(int u,int t){
top[u]=t;
rk[dfn[u]=++cur]=u;
if(!son[u]){
return;
}
dfs2(son[u],t);
go(i,u){
int v=e[i].to;
if(v==fa[u][0]||v==son[u]){
continue;
}
dfs2(v,v);
}
}
struct SGT{
ll tr[N<<2],f[N<<2][3],tag[N<<2][3];
il void reset(int o,int op,int k){
tr[o]+=f[o][op]*k;
tag[o][op]+=k;
}
il void pushup(int o){
tr[o]=tr[o<<1]+tr[o<<1|1];
}
il void pushdown(int o){
rep(i,0,2){
reset(o<<1,i,tag[o][i]),reset(o<<1|1,i,tag[o][i]);
tag[o][i]=0;
}
}
void build(int l,int r,int o){
if(l==r){
if(l>1){
f[o][0]=1;
f[o][1]=siz[rk[l]];
f[o][2]=-dep[rk[l]];
}
return;
}
int mid=(l+r)>>1;
build(l,mid,o<<1),build(mid+1,r,o<<1|1);
f[o][0]=f[o<<1][0]+f[o<<1|1][0];
f[o][1]=f[o<<1][1]+f[o<<1|1][1];
f[o][2]=f[o<<1][2]+f[o<<1|1][2];
}
void update(int l,int r,int o,int x,int y,int op,int k){
if(l>=x&&r<=y){
reset(o,op,k);
return;
}
pushdown(o);
int mid=(l+r)>>1;
if(x<=mid){
update(l,mid,o<<1,x,y,op,k);
}
if(y>mid){
update(mid+1,r,o<<1|1,x,y,op,k);
}
pushup(o);
}
ll query(int l,int r,int o,int x,int y){
if(r<x||l>y){
return 0;
}
if(l>=x&&r<=y){
return tr[o];
}
pushdown(o);
int mid=(l+r)>>1;
return query(l,mid,o<<1,x,y)+query(mid+1,r,o<<1|1,x,y);
}
}T;
il int jump(int u,int k){
drep(i,18,0){
if(k>=(1<<i)){
u=fa[u][i];
k-=1<<i;
}
}
return u;
}
il int getLca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
u=fa[top[u]][0];
}
return dep[u]<dep[v]?u:v;
}
il void update(int u,int v,int op,int k){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
T.update(1,n,1,dfn[top[u]],dfn[u],op,k);
u=fa[top[u]][0];
}
if(dfn[u]>dfn[v]){
swap(u,v);
}
if(dfn[u]<dfn[v]){
T.update(1,n,1,dfn[u]+1,dfn[v],op,k);
}
}
il ll query(int u,int v){
ll ret=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
ret+=T.query(1,n,1,dfn[top[u]],dfn[u]);
u=fa[top[u]][0];
}
if(dfn[u]>dfn[v]){
swap(u,v);
}
if(dfn[u]<dfn[v]){
ret+=T.query(1,n,1,dfn[u]+1,dfn[v]);
}
return ret;
}
void Yorushika(){
read(n);
rep(i,1,n-1){
int u,v;read(u,v);
add(u,v),add(v,u);
}
dfs1(1,0),dfs2(1,1);
T.build(1,n,1);
read(m);
ll sum=0;
while(m--){
int op,x,y;
read(op,x);
if(op==1){
read(y);
if(x==y){
x=y=1;
}
if(dep[x]<=dep[y]||jump(x,dep[x]-dep[y])!=y){
T.update(1,n,1,dfn[y],dfn[y]+siz[y]-1,1,1);
update(1,fa[y][0],0,siz[y]);
sum+=siz[y];
}else{
int u=jump(x,dep[x]-dep[y]-1);
T.update(1,n,1,1,dfn[u]-1,1,1);
T.update(1,n,1,dfn[u]+siz[u],n,1,1);
update(1,y,0,-siz[u]);
sum+=n-siz[u];
}
}else if(op==2){
read(y);
int u=getLca(x,y);
update(x,u,2,1),update(x,u,0,1+dep[x]);
update(y,u,2,1),update(y,u,0,1+dep[y]);
update(1,u,0,dep[x]+dep[y]-2*dep[u]+1);
sum+=dep[x]+dep[y]-2*dep[u]+1;
}else{
ll ans=T.tr[1];
if(x==1){
printf("%lld\n",ans);
}else{
ans+=1ll*(dep[x]-1)*sum-2*query(1,x);
printf("%lld\n",ans);
}
}
assert(!T.query(1,n,1,1,1));
}
}
signed main(){
int t=1;
//read(t);
while(t--){
Yorushika();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 10068kb
input:
5 4 2 2 5 1 5 1 3 5 2 2 4 3 4 2 1 5 2 5 5 3 2
output:
1 5
result:
ok 2 number(s): "1 5"
Test #2:
score: -100
Wrong Answer
time: 110ms
memory: 12136kb
input:
200 171 114 50 183 28 68 67 152 139 125 67 55 50 98 106 71 46 42 157 165 42 49 113 12 81 145 105 13 38 96 34 156 24 17 21 191 135 54 174 116 177 157 123 71 95 130 135 193 150 129 25 190 96 93 188 173 90 160 86 187 20 132 199 75 59 195 189 24 40 68 163 83 25 13 73 33 59 50 154 19 146 21 151 67 89 69 ...
output:
826 908 813 1785 2288 1320 3038 2403 4809 3933 4123 3791 5819 4597 6632 7523 4562 8021 7393 9809 7647 6024 11272 7024 12979 14995 9349 9115 8437 11003 18272 22174 16139 17660 11063 14291 12045 18630 12368 17355 23696 20714 24792 20021 13962 22060 13163 19488 13321 25000 19336 30022 19846 33622 17483...
result:
wrong answer 2782nd numbers differ - expected: '1132082', found: '1131891'