QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#419982#8716. 树yangyuchen17WA 0ms9712kbC++142.3kb2024-05-24 13:35:422024-05-24 13:35:44

Judging History

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

  • [2024-05-24 13:35:44]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9712kb
  • [2024-05-24 13:35:42]
  • 提交

answer

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

int n,m,q,b[N],deep[N],f[N][20];
int a[N],c[N];
int h[N],e[M],ne[M],idx;

void add(int u,int v){
    e[idx]=v,ne[idx]=h[u],h[u]=idx++;
}

bool vis[N];
void dfs1(int u){
    vis[u]=true;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(vis[v]) continue;
        deep[v]=deep[u]+1;
        f[v][0]=u;
        for(int j=1;j<20;j++) f[v][j]=f[f[v][j-1]][j-1];
        dfs1(v);
    }
}

int main(){
    cin>>n>>m>>q;
    memset(h,-1,sizeof h);
    a[1]=c[n]=-1;
    int u,v,ans=2;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    dfs1(1);
    cin>>b[1];
    for(int i=2;i<=m;i++){
        cin>>b[i];
        int x=b[i],y=b[i-1],d=deep[b[i]]-deep[b[i-1]],cnt=0;
        if(d<0) d=-d,swap(x,y);
        if(d){
        	d--;
			while(d){
        		if(d&1) x=f[x][cnt];
        		d>>=1,cnt++;
			}
			if(f[x][0]==y){
				if(deep[b[i]]>deep[b[i-1]]) c[i-1]=x,a[i]=0;
				else a[i]=x,c[i-1]=0;
			}else a[i]=c[i-1]=0;
		}else a[i]=c[i-1]=0;
		if(a[i-1]==c[i-1]) ans++;
    }
    int i;
    while(q--){
        cin>>i>>u;
        b[i]=u;
        if(a[i]==c[i]) ans--;
        if(i!=n){
        	if(a[i+1]==c[i+1]) ans--;
        	int x=b[i+1],y=b[i],d=deep[x]-deep[y],cnt=0;
    	    if(d<0) d=-d,swap(x,y);
    	    a[i+1]=f[b[i+1]][0],c[i]=f[b[i]][0];
    	    if(d){
    	    	d--;
    	   		while(d){
    	    		if(d&1) x=f[x][cnt];
    	    		d>>=1,cnt++;
				}
				if(f[x][0]==y){
					if(deep[b[i+1]]>deep[b[i]]) c[i]=x;
					else a[i+1]=x;
				}
			}
			if(a[i+1]==c[i+1]) ans++;
		}
		if(i!=1){
			if(a[i-1]==c[i-1]) ans--;
			int x=b[i],y=b[i-1],d=deep[x]-deep[y],cnt=0;
    	    if(d<0) d=-d,swap(x,y);
    	    a[i]=f[b[i]][0],c[i-1]=f[b[i-1]][0];
    	    if(d){
    	 		d--;
    	 		while(d){
    	  	  	if(d&1) x=f[x][cnt];
    	    		d>>=1,cnt++;
				}
				if(f[x][0]==y){
					if(deep[b[i]]>deep[b[i-1]]) c[i-1]=x;
					else a[i]=x;
				}	
			}
			if(a[i-1]==c[i-1]) ans++;
		}
		if(a[i]==c[i]) ans++;
        cout<<ans<<endl;
        /*
        for(int i=1;i<=m;i++){
            cout<<b[i]<<":"<<a[i]<<" "<<c[i]<<endl;
        }
        */
    }
    return 0;
}
/*
5 5 3
2 1
3 2
1 4
5 1
1 5 4 2 3
1 3
5 3
3 3
*/

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 9712kb

input:

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

output:

3
3
5

result:

wrong answer 1st numbers differ - expected: '4', found: '3'