QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#603449#8716. 树ZariaRE 0ms17472kbC++142.2kb2024-10-01 16:37:222024-10-01 16:37:23

Judging History

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

  • [2024-10-01 16:37:23]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:17472kb
  • [2024-10-01 16:37:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define PLL pair<ll,ll>
const ll N=2e5+10;

ll h[N],ne[N*2],e[N*2],idx;
ll bb[N],res[N];
ll n,m,q;
ll fa[20][N],d[N];
bool st[N];

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

void dfs(int x){
    st[x]=true;
    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]){
        if(st[e[i]]!=true){
            st[e[i]]=true;
            d[e[i]]=d[x]+1;
            fa[e[i]][0]=x;
            dfs(e[i]);
        }
    }
}

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=20;i>=0;i--){
        if(fa[a][i]==fa[b][i]) continue;
        a=fa[a][i];
        b=fa[b][i];
    }

    return fa[a][0];
}

bool is_gl(ll a,ll b,ll c){
    ll t=lca(a,c);
    if(b==t) return true;
    if(t==a){
        ll t1=lca(t,b),t2=lca(b,c);
        if(t1==a&&t2==b){
            return true;
        }    
        return false;
    }
    if(t==c){
        ll t1=lca(t,c),t2=lca(b,a);
        if(t1==c&&t2==b){
            return true;
        }    
        return false;
    }
    ll t1=lca(b,a),t2=lca(b,c);
    if(t1==t&&t2==b) return true;
    if(t1==b&&t2==t) return true;
    return false;
}

int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        ll 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];
    }
    res[1]=res[n]=1;
    for(int i=2;i<n;i++){
        if(!is_gl(bb[i-1],bb[i],bb[i+1])){
            res[i]=1;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=res[i];
    }
    for(int i=1;i<=q;i++){
        ll p,w;
        cin>>p>>w;
        bb[p]=w;
        for(int j=max(2ll,p-1);j<=min(n-1,p+1);j++){
            ans-=res[j];
            if(!is_gl(bb[j-1],bb[j],bb[j+1])){
                res[j]=1;
            }
            else res[j]=0;
            ans+=res[j];
        }
        cout<<ans<<endl;
    }
    return 0;
}

详细

Test #1:

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

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
Runtime Error

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:


result: