QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#509535 | #1163. Another Tree Queries Problem | xlwang | WA | 131ms | 34512kb | C++14 | 8.0kb | 2024-08-08 15:45:35 | 2024-08-08 15:45:37 |
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--){
// cerr<<q<<endl;
int tp=read();
if(tp==1){
int x,y;
x=read();y=read();
if(dfn[x]>dfn[y]) swap(x,y);
if(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;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 30252kb
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: 131ms
memory: 34512kb
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:
1331 1069 1566 2662 5126 3260 6622 7275 13552 12363 10710 11172 16901 13644 17820 21049 13231 18035 20345 24924 17326 16790 26056 15902 29519 35074 21740 22316 17778 19950 34901 36687 29982 30727 18533 24747 23092 31697 23351 26007 35709 33505 41151 33708 22646 33576 21238 31664 21432 39921 32433 49...
result:
wrong answer 1st numbers differ - expected: '826', found: '1331'