QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#509563 | #1163. Another Tree Queries Problem | xlwang | RE | 0ms | 32308kb | C++14 | 8.2kb | 2024-08-08 16:05:04 | 2024-08-08 16:05:04 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define fr(i,j,k) for(register int i=j;i<=k;++i)
#define rf(i,j,k) for(register int i=j;i>=k;--i)
#define foredge(i,j) for(register int i=head[j];i;i=e[i].nxt)
#define pb push_back
#define Times printf("Time:%.3lf\n",clock()/CLOCKS_PER_SEC)
#define pii pair<int,int>
#define mk make_pair
using namespace std;
inline int read(){
int x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return f?-x:x;
}
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void writeln(int x){write(x); puts("");}
inline void writepl(int x){write(x); putchar(' ');}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int randfind(int l,int r){return rnd()%(r-l+1)+l;}
//inline void init(){
// int t=read();
// while(t--) work();
//}
const int Maxn=2e5+10;
struct sgt1{
int s[Maxn<<2],tag[Maxn<<2];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void pushup(int x){s[x]=s[ls(x)]+s[rs(x)];}
inline void change(int x,int l,int r,int k){s[x]+=1ll*(r-l+1)*k;tag[x]+=k;}
inline void pushdown(int x,int l,int r){
if(tag[x]){
int mid;mid=(l+r)>>1;
change(ls(x),l,mid,tag[x]);change(rs(x),mid+1,r,tag[x]);
tag[x]=0;
}
}
inline void update(int ql,int qr,int l,int r,int x,int k){
if(ql<=l && r<=qr){change(x,l,r,k);return;}
pushdown(x,l,r);int mid;mid=(l+r)>>1;
if(ql<=mid) update(ql,qr,l,mid,ls(x),k);
if(mid<qr) update(ql,qr,mid+1,r,rs(x),k);
pushup(x);
}
inline int query(int ql,int qr,int l,int r,int x){
if(ql<=l && r<=qr) return s[x];
pushdown(x,l,r);
int mid;mid=(l+r)>>1;int ans=0;
if(ql<=mid) ans+=query(ql,qr,l,mid,ls(x));
if(mid<qr) ans+=query(ql,qr,mid+1,r,rs(x));
return ans;
}
}T1,T5;
int a[Maxn];
struct sgt2{
int s[Maxn<<2],tag[Maxn<<2],tr[Maxn<<2];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void pushup(int x){
s[x]=s[ls(x)]+s[rs(x)];
// cout<<"pushup:"<<x<<' '<<s[x]<<endl;
}
inline void build(int x,int l,int r){
if(l==r){tr[x]=a[l];return;}
int mid;mid=(l+r)>>1;
build(ls(x),l,mid);build(rs(x),mid+1,r);
tr[x]=tr[ls(x)]+tr[rs(x)];
}
inline void change(int x,int k){s[x]+=tr[x]*k;tag[x]+=k;}
inline void pushdown(int x){
if(tag[x]){change(ls(x),tag[x]);change(rs(x),tag[x]);tag[x]=0;}
}
inline void update(int ql,int qr,int l,int r,int x,int k){
// cout<<ql<<' '<<qr<<' '<<l<<' '<<r<<' '<<x<<' '<<k<<endl;
if(ql<=l && r<=qr){
// cout<<"*"<<l<<' '<<r<<' '<<x<<' '<<tr[x]<<' '<<k<<endl;
change(x,k);return;
}
pushdown(x);
int mid;mid=(l+r)>>1;
if(ql<=mid) update(ql,qr,l,mid,ls(x),k);
if(mid<qr) update(ql,qr,mid+1,r,rs(x),k);
pushup(x);
}
inline int query(int ql,int qr,int l,int r,int x){
if(ql<=l && r<=qr) return s[x];
pushdown(x);
int mid;mid=(l+r)>>1;int ans=0;
if(ql<=mid) ans+=query(ql,qr,l,mid,ls(x));
if(mid<qr) ans+=query(ql,qr,mid+1,r,rs(x));
return ans;
}
}T2,T3,T4;
int n,q;
vector<int> vc[Maxn];
int dep[Maxn],siz[Maxn],dfn[Maxn],top[Maxn],father[Maxn],son[Maxn],idx;
inline int getmin(int x,int y){if(dep[x]<dep[y]) return x;return y;}
namespace LCA{
int dfn[Maxn],f[Maxn<<2][21],lg[Maxn<<2];
int nod;
inline void dfs(int x,int fa){
dfn[x]=++nod;f[nod][0]=x;
for(auto y:vc[x]) if(y!=fa) dfs(y,x),f[++nod][0]=x;
}
inline void init(){
dfs(1,0);lg[0]=-1;fr(i,1,nod) lg[i]=lg[i/2]+1;
fr(j,1,lg[nod]) fr(i,1,nod){
if(i+(1<<j)-1>nod) break;
f[i][j]=getmin(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
inline int getlca(int l,int r){
l=dfn[l],r=dfn[r];if(l>r) swap(l,r);
int ln=lg[r-l+1];
return getmin(f[l][ln],f[r-(1<<ln)+1][ln]);
}
}
int Fa[Maxn][25];
inline void dfs1(int x,int fa){
dep[x]=dep[fa]+1;father[x]=fa;siz[x]=1;
Fa[x][0]=fa;fr(i,1,20) Fa[x][i]=Fa[Fa[x][i-1]][i-1];
for(auto y:vc[x]) if(y!=fa){
dfs1(y,x),siz[x]+=siz[y];
if(!son[x] || siz[son[x]]<siz[y]) son[x]=y;
}
}
inline void dfs2(int x,int fa,int tp){
dfn[x]=++idx;top[x]=tp;
if(son[x]) dfs2(son[x],x,tp);
for(auto y:vc[x]) if(y!=fa && y!=son[x]) dfs2(y,x,y);
}
inline void init(){
n=read();
fr(i,1,n-1){
int x,y;
x=read();y=read();
vc[x].pb(y);vc[y].pb(x);
}
// cerr<<"**"<<endl;
dfs1(1,0);dfs2(1,0,1);LCA::init();
// cerr<<"**"<<endl;
fr(i,1,n) a[dfn[i]]=dep[i];T2.build(1,1,n);T4.build(1,1,n);
fr(i,1,n) a[dfn[i]]=siz[i];T3.build(1,1,n);
}
inline int getans(int l,int r){
if(l>r) return 0;
return T1.query(l,r,1,n,1)+T2.query(l,r,1,n,1)+T3.query(l,r,1,n,1);
}
inline int query(int x){
int ans=T4.query(1,n,1,n,1)+1ll*dep[x]*T5.query(1,n,1,n,1);
// cout<<T4.query(1,n,1,n,1)<<endl;
// fr(i,1,n) cout<<i<<' '<<T4.query(i,i,1,n,1)<<endl;
// cout<<T5.query(1,n,1,n,1)*dep[x]<<endl;
// cout<<ans<<endl;
// cout<<T1.query(1,n,1,n,1)<<' '<<T2.query(1,n,1,n,1)<<' '<<T3.query(1,n,1,n,1)<<endl;
while(x){
ans-=2*getans(dfn[top[x]],dfn[x]);
x=father[top[x]];
}return ans;
}
inline void update(int x,int k){
while(x){
T1.update(dfn[top[x]],dfn[x],1,n,1,k);
x=father[top[x]];
}
}
inline void update1(int x,int k){
T3.update(dfn[x],dfn[x]+siz[x]-1,1,n,1,k);
update(father[x],k*siz[x]);
}
inline void change2(int x,int llca){
update(x,dep[x]+1);update(father[llca],-dep[x]-1);
while(top[x]!=top[llca]){
// cout<<dfn[top[x]]<<' '<<dfn[x]<<endl;
T2.update(dfn[top[x]],dfn[x],1,n,1,-1);
T4.update(dfn[top[x]],dfn[x],1,n,1,1);
T5.update(dfn[top[x]],dfn[x],1,n,1,1);
x=father[top[x]];
}
// cout<<dfn[llca]<<' '<<dfn[x]<<' '<<T1.query(3,4,1,n,1)<<endl;
T2.update(dfn[llca],dfn[x],1,n,1,-1);
T4.update(dfn[llca],dfn[x],1,n,1,1);
T5.update(dfn[llca],dfn[x],1,n,1,1);
// cout<<dfn[llca]<<' '<<dfn[x]<<' '<<T2.query(3,4,1,n,1)<<endl;
}
inline void update2(int x,int y){
int llca=LCA::getlca(x,y);
// cout<<x<<' '<<y<<' '<<llca<<endl;
if(x==y){
update(x,1);
T5.update(dfn[x],dfn[x],1,n,1,1);
T4.update(dfn[x],dfn[x],1,n,1,1);
return;
}
if(x!=llca) change2(x,llca);
if(y!=llca) change2(y,llca);
if(x!=llca && y!=llca){
T1.update(dfn[llca],dfn[llca],1,n,1,-1);
T4.update(dfn[llca],dfn[llca],1,n,1,-1);
T5.update(dfn[llca],dfn[llca],1,n,1,-1);
}
update(father[llca],dep[x]+dep[y]-2*dep[llca]+1);
// cout<<T1.query(1,2,1,n,1)<<' '<<T1.query(3,4,1,n,1)<<' '<<T1.query(1,n,1,n,1)<<endl;
}
inline void work(){
int q=read();
while(q--){
int tp=read();
if(tp==1){
int x,y;
y=read();x=read();
if(dfn[x]<=dfn[y] && dfn[y]<=dfn[x]+siz[x]-1){
int Up=dep[y]-dep[x]-1;
fr(i,0,20) if((1<<i)&Up) y=Fa[y][i];
update1(1,1),update1(y,-1);
T4.update(dfn[y],dfn[y]+siz[y]-1,1,n,1,-1);
T4.update(1,n,1,n,1,1);
T5.update(dfn[y],dfn[y]+siz[y]-1,1,n,1,-1);
T5.update(1,n,1,n,1,1);
}
else{
update1(x,1);
T4.update(dfn[x],dfn[x]+siz[x]-1,1,n,1,1);
T5.update(dfn[x],dfn[x]+siz[x]-1,1,n,1,1);
}
}
if(tp==2){int x,y;x=read();y=read();update2(x,y);}
if(tp==3){int x;x=read();writeln(query(x));}
// cout<<"*"<<q<<endl;
// fr(i,1,n) cout<<i<<' '<<T4.query(i,i,1,n,1)<<endl;
}
}
signed main(){
// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
init();work();
// printf("\nTIME:%.3lf",(double)clock()/CLOCKS_PER_SEC);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 32308kb
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
Runtime Error
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 ...