QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#603495#8716. 树ZariaWA 0ms16168kbC++174.4kb2024-10-01 16:55:282024-10-01 16:55:29

Judging History

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

  • [2024-10-01 16:55:29]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:16168kb
  • [2024-10-01 16:55:28]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
 
#define PLL pair<ll,ll>
#define ll long long
const ll N=2e5+10,mod=1e9+7;
ll n,m,q;
ll h[N],ne[N*2],e[N*2],idx;
ll bb[N],st[N];
ll fa[N][20],d[N],ud[N];
ll root;
bool sst[N];

void add(ll m,ll n){
    e[idx]=n,ne[idx]=h[m],h[m]=idx++;
}

void dfs(ll x){
    sst[x]=1;
    for(int i=1;(1<<i)<=d[x];i++)
    fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=h[x];i!=-1;i=ne[i]){
        ll j=e[i];
        if(sst[j]==0){
            d[j]=d[x]+1;
            fa[j][0]=x;
            dfs(j);
        }
    }
}

ll lca(ll a,ll b){
    if(d[a]<d[b]) swap(a,b);

    for(int i=18;i>=0;i--){
        if(d[fa[a][i]]<d[b]) continue;
        a=fa[a][i];
    }

    if(a==b) return a;
    for(int i=18;i>=0;i--){
        if(fa[a][i]==fa[b][i]) continue;
        a=fa[a][i];
        b=fa[b][i];
    }

    return fa[a][0];
}

int main(){
    cin>>n>>m>>q;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }

    d[1]=1;
    dfs(1);
    
    for(int i=1;i<=m;i++){
        cin>>bb[i];
    }
    ud[1]=0;
    st[1]=1;
    ll t=lca(bb[1],bb[2]);
    if(t==bb[1]){
        ud[2]=1;//1 下 2 上
    }
    if(t==bb[2]){
        ud[2]=2;
    }
    if(t!=bb[1]&&t!=bb[2]){
        ud[2]=1;
    }
    for(int i=2;i<n;i++){
        t=lca(bb[i],bb[i+1]);
        if(t!=bb[i]&&t!=bb[i+1]){
            ud[i+1]=1;
            st[i]=1;
        }
        if(t==bb[i]){
            if(ud[i]==2){
                st[i]=1;
                ud[i+1]=1;
            }
            else{
                st[i]=0;
                ud[i+1]=1;
            }
        }
        if(t==bb[i+1]){
            if(ud[i]==2){
                st[i]=0;
                ud[i+1]=2;
            }
            else{
                st[i]=1;
                ud[i+1]=2;
            }
        }
    }
    ll res=0;
    st[n]=1;

    for(int i=1;i<=n;i++){
        if(st[i]==1) res++;
    }

    for(int i=1;i<=q;i++){
        ll p,w;
        cin>>p>>w;
        bb[p]=w;
        if(p==1){
            ll pre=ud[2];
            t=lca(bb[1],bb[2]);
            if(t==bb[1]){
                ud[2]=1;//1 下 2 上
            }
            if(t==bb[2]){
                ud[2]=2;
            }
            if(t!=bb[1]&&t!=bb[2]){
                ud[2]=1;
            }
            if(pre!=ud[2]){
                pre=st[2];
                if(ud[2]==ud[3]){
                    st[2]==0;
                }
                else{
                    st[2]==1;
                }
                res+=st[2]-pre;
            }
        }
        if(p==n){
            ll pre=ud[n];
            t=lca(bb[n-1],bb[n]);
            if(t==bb[n]){
                ud[n]=2;//1 下 2 上
                if(pre!=ud[n]){
                    pre=st[n-1];
                    st[n-1]=1;
                    res+=st[n-1]-pre;
                }
            }
            if(t==bb[n-1]){
                ud[n]=1;
                if(pre!=ud[n]){
                    pre=st[n-1];
                    st[n-1]=1;
                    res+=st[n-1]-pre;
                }
            }
            if(t!=bb[n-1]&&t!=bb[n]){
                ud[n]=1;
                if(pre!=ud[n]){
                    pre=st[n-1];
                    st[n-1]=1;
                    res+=st[n-1]-pre;
                }
            }
        }
        if(p!=1&&p!=n){
            ll pre=st[p-1]+st[p]+st[p+1];
            for(int j=p-1;j<=p+1;j++){
                t=lca(bb[j],bb[j+1]);
                if(t!=bb[j]&&t!=bb[j+1]){
                    ud[j+1]=1;
                    st[j]=1;
                }
                if(t==bb[j]){
                    if(ud[j]==2){
                        st[j]=1;
                        ud[j+1]=1;
                    }
                    else{
                        st[j]=0;
                        ud[j+1]=1;
                    }
                }
                if(t==bb[j+1]){
                    if(ud[j]==2){
                        st[j]=0;
                        ud[j+1]=2;
                    }
                    else{
                        st[j]=1;
                        ud[j+1]=2;
                    }
                }
            }
            res+=st[p-1]+st[p]+st[p+1]-pre;
        }
        cout<<res<<endl;
    }
    return 0;
}

詳細信息

Test #1:

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

input:

5 5 3
2 1
3 2
1 4
5 1
1 5 4 2 3
1 3
5 3
3 3

output:

4
4
5

result:

ok 3 number(s): "4 4 5"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 16168kb

input:

30 200 200
10 24
10 13
10 26
13 29
27 26
17 24
27 21
17 15
13 5
13 30
27 3
18 21
9 21
2 24
10 4
11 5
2 8
10 23
1 18
21 25
4 20
12 23
22 27
28 27
18 7
13 6
14 30
10 19
16 21
14 29 25 30 1 17 22 21 11 19 21 30 13 1 22 10 14 7 29 7 15 21 25 29 25 7 29 7 1 23 3 17 2 7 4 27 18 26 3 6 5 3 16 26 20 19 16 2...

output:

28
31
33
33
36
39
39
41
43
46
48
51
54
57
60
63
64
67
69
69
72
73
75
77
79
81
84
84
86
88
88
88
89
89
92
95
96
98
101
101
101
104
105
106
109
110
112
114
115
115
116
117
119
119
119
120
120
120
123
125
125
128
130
130
130
130
129
131
131
134
135
135
135
135
134
137
138
138
138
141
142
142
145
148
14...

result:

wrong answer 1st numbers differ - expected: '174', found: '28'