QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#475325#1163. Another Tree Queries Problemlichenyu_acTL 0ms35112kbC++144.0kb2024-07-13 14:03:222024-07-13 14:03:23

Judging History

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

  • [2024-07-13 14:03:23]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:35112kb
  • [2024-07-13 14:03:22]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e5+10,M=N*2;

int head[N],ver[M],nxt[M],tot=1;
void add(int x,int y){
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}

int n,m,ans;
int d[N],fa[N],s[N],to[N];
int dfn[N],id[N],top[N],cnt;

void dfs1(int x,int father){
    fa[x]=father,d[x]=d[father]+1,s[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==father)continue;
        dfs1(y,x);
        s[x]+=s[y];
        if(s[y]>s[to[x]])to[x]=y;
    }
}

void dfs2(int x,int t){
    dfn[x]=++cnt,id[cnt]=x,top[x]=t;
    if(to[x])dfs2(to[x],t);
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa[x]||y==to[x])continue;
        dfs2(y,y);
    }
}

int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    return d[x]<d[y]?x:y;
}

int get_son(int x,int y){
    int ret=0;
    while(top[x]!=top[y]){
        ret=top[x];
        x=fa[top[x]];
    }

    if(x==y)return ret;
    else return to[y];
}

#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((L+R)>>1)

ll dat[N<<2],sum_size[N<<2],sum_dep[N<<2],len[N<<2];

struct Tag{
    ll a,s,d;
    Tag():a(0),s(0),d(0){}
    Tag(ll a,ll s,ll d):a(a),s(s),d(d){}
    operator bool(){
        return a||s||d;
    }
    void operator+=(const Tag &t){
        a+=t.a,s+=t.s,d+=t.d;
    }
}tag[N<<2];

void upd(int p){
    dat[p]=dat[lc]+dat[rc];
}

void change(int p,const Tag &t){
    dat[p]+=t.a*len[p]+t.s*sum_size[p]+t.d*sum_dep[p];
    tag[p]+=t;
}

void spread(int p){
    if(tag[p]){
        change(lc,tag[p]),change(rc,tag[p]);
        tag[p]=Tag();
    }
}

void build(int p,int L,int R){
    len[p]=R-L+1;
    if(L==R){
        sum_size[p]=s[id[L]];
        sum_dep[p]=d[id[L]];
        return;
    }
    build(lc,L,mid),build(rc,mid+1,R);
    sum_size[p]=sum_size[lc]+sum_size[rc];
    sum_dep[p]=sum_dep[lc]+sum_dep[rc];
}

void change(int p,int L,int R,int l,int r,const Tag &t){
    if(l<=L&&R<=r){
        change(p,t);
        return;
    }
    spread(p);
    if(l<=mid)change(lc,L,mid,l,r,t);
    if(r>mid)change(rc,mid+1,R,l,r,t);
    upd(p);
}

ll ask(int p,int L,int R,int l,int r){
    if(l<=L&&R<=r)return dat[p];
    spread(p);
    if(r<=mid)return ask(lc,L,mid,l,r);
    else if(l>mid)return ask(rc,mid+1,R,l,r);
    else return ask(lc,L,mid,l,r)+ask(rc,mid+1,R,l,r);
}

#undef lc
#undef rc
#undef mid

void change_subtree(int x,int k){
    change(1,1,n,dfn[x],dfn[x]+s[x]-1,Tag(0,k,0));
    k*=s[x],ans+=k;
    for(x=fa[x];x;x=fa[top[x]])change(1,1,n,dfn[top[x]],dfn[x],Tag(k,0,0));
}

void change_chain(int x,int y){
    int p=LCA(x,y),dx=d[x]+1,dy=d[y]+1,dist=dx+dy-1-d[p]*2;
    ans+=dist;
    while(top[x]!=top[p]){
        change(1,1,n,dfn[top[x]],dfn[x],Tag(dx,0,-1));
    }
    if(x!=p)change(1,1,n,dfn[p]+1,dfn[x],Tag(dx,0,-1));
    while(top[y]!=top[p]){
        change(1,1,n,dfn[top[y]],dfn[y],Tag(dy,0,-1));
    }
    if(y!=p)change(1,1,n,dfn[p]+1,dfn[y],Tag(dy,0,-1));
    for(;p;p=fa[top[p]])change(1,1,n,dfn[top[p]],dfn[p],Tag(dist,0,0));
}

ll ask(int x){
    ll ret=d[x]*ans+dat[1];
    while(x){
        ret-=2*ask(1,1,n,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    return ret;
}

int main(){
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dfs1(1,0),dfs2(1,1),build(1,1,n);
    scanf("%d",&m);
    while(m--){
        int op,x,y;
        scanf("%d%d",&op,&x);
        if(op==1){
            scanf("%d",&y);
            if(x==y)change_subtree(1,1);
            else if(dfn[y]<dfn[x]&&dfn[x]<dfn[y]+s[y]){
                change_subtree(1,1);
                change_subtree(get_son(x,y),-1);
            }else change_subtree(y,1);
        }else if(op==2){
            scanf("%d",&y);
            change_chain(x,y);
        }else printf("%lld\n",ask(x));
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 35112kb

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
Time Limit Exceeded

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:


result: