QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#509535#1163. Another Tree Queries ProblemxlwangWA 131ms34512kbC++148.0kb2024-08-08 15:45:352024-08-08 15:45:37

Judging History

你现在查看的是最新测评结果

  • [2024-08-08 15:45:37]
  • 评测
  • 测评结果:WA
  • 用时:131ms
  • 内存:34512kb
  • [2024-08-08 15:45:35]
  • 提交

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'