QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#509541 | #1163. Another Tree Queries Problem | xlwang | WA | 127ms | 38480kb | C++14 | 8.0kb | 2024-08-08 15:53:40 | 2024-08-08 15:53:40 |
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]);
}
}
inline void dfs1(int x,int fa){
dep[x]=dep[fa]+1;father[x]=fa;siz[x]=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);
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){
update1(1,1),update(x,-1);
T4.update(dfn[x],dfn[x]+siz[x]-1,1,n,1,-1);
T4.update(1,n,1,n,1,1);
T5.update(dfn[x],dfn[x]+siz[x]-1,1,n,1,-1);
T5.update(1,n,1,n,1,1);
T1.update(dfn[x],dfn[x],1,n,1,siz[x]);
}
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));}
}
}
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: 38480kb
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: 127ms
memory: 22196kb
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:
841 923 828 1806 2319 1351 3069 2442 4851 3975 4165 3833 5861 4639 6682 7587 4627 8086 7460 9876 7715 6092 11340 7098 13061 15078 9432 9198 8408 10850 18262 21982 16107 17252 10920 14041 12066 18225 12402 17088 23394 20428 24617 19666 13687 21781 12929 19254 13118 24503 19268 29882 19787 33060 17218...
result:
wrong answer 1st numbers differ - expected: '826', found: '841'