QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#602629#8716. 树AAA___#RE 0ms0kbC++143.8kb2024-10-01 11:21:172024-10-01 11:21:18

Judging History

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

  • [2024-10-01 11:21:18]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-01 11:21:17]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include<stack>
#include<set>
#include<unordered_set>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<map>
#include<string>
#include<vector>
#include<array>
#include<functional>
using namespace std;
typedef long long ll;
ll highbit(ll x){
    ll ans=2;
    int num=1;
    while(x){
        x>>=2;
        ans<<=2;
        num++;
    }
    return num;
}
ll lowbit(ll x){
    return x&(-x);
}
long long max(long long a,long long b){
    return a>b?a:b;
}
long long min(long long a,long long b){
    return a>b?b:a;
}
ll gcd(ll x,ll y)
{
    if(y==1)
        return x;
    return gcd(y,x%y);
}

const int maxn=4e5;
vector<int> G[maxn];
int arr[maxn];
struct WANDL{
    int size[maxn],dep[maxn],son[maxn],top[maxn],fa[maxn];
    void dfs(int x,int pre){
        fa[x]=pre;
        size[x]=1;
        dep[x]=dep[pre]+1;
        son[x]=0;
        for(auto i:G[x]){
            if(i==pre){
                continue;
            }
            dfs(i,x);
            size[x]+=size[i];
            if(size[i]>size[son[x]]){
                son[x]=i;
            }
        }
        return;        
    }
    void dfstop(int x,int pre,int t){
        top[x]=t;
        if(!son[x]){
            return;
        }
        for(auto i:G[x]){
            if(i==pre){
                continue;
            }
            if(i==son[x]){
                dfstop(i,x,top[x]);
            }else{
                dfstop(i,x,i);
            }
        }
        return ;
    }
    void init(int root){
        dep[0]=-1;
        dfs(root,0);
        dfstop(root,0,root);
    }
    int lca(int a,int b){
        while(top[a]!=top[b]){
        if(dep[top[a]]<dep[top[b]]){
            swap(a,b);
        }
        a=fa[top[a]];
        }
        return (dep[a]>dep[b]?b:a);       
    }
}wdl;
bool judge(int u,int x,int v){
    if(u==v){
        return false;
    }
    int f=wdl.lca(u,v);
    if(f!=u&&f!=v){
        if(wdl.lca(f,x)==x){
            return true;
        }
    }else{
        if(f==u){
            if(wdl.lca(v,x)==x){
                return true;
            }
        }else{
            if(wdl.lca(u,x)==x){
                return true;
            }
        }
    }
    if(f==wdl.lca(u,x)&&wdl.lca(v,x)==x){
        return true;
    }
    return false;
}
void solve() {
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    wdl.init(1);
    for(int i=1;i<=m;i++){
        cin>>arr[i];
    }
    ll ans=2;
    for(int i=3;i<=m;i++){
        if(!judge(arr[i-2],arr[i-1],arr[i])){
            ans++;
        }
    }
    if(m==2){
        while(q--){
            cout<<2<<endl;
        }
        return ;
    }
    while(q--){
        int p,x;
        cin>>p>>x;
        ll b1=0,b2=0;
        if(p+1<=m&&p-1>=1){
            if(!judge(arr[p-1],arr[p],arr[p+1])){
                b1++;
            }
            if(!judge(arr[p-1],x,arr[p+1])){
                b2++;
            }
        }
        if(p+2<=m){
            if(!judge(arr[p],arr[p+1],arr[p+2])){
                b1++;
            }
            if(!judge(x,arr[p+1],arr[p+2])){
                b2++;
            }
        }
        if(p-2>=1){
            if(!judge(arr[p-2],arr[p-1],arr[p])){
                b1++;
            }
            if(!judge(arr[p-2],arr[p-1],x)){
                b2++;
            }
        }
        ans+=(b2-b1);
        cout<<ans<<endl;
        arr[p]=x;
    }
    return ;
}
int main(void){
    unsigned int t;
    //freopen("input.in","r",stdin);
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 1;
}

詳細信息

Test #1:

score: 0
Runtime Error

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: