QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#419982 | #8716. 树 | yangyuchen17 | WA | 0ms | 9712kb | C++14 | 2.3kb | 2024-05-24 13:35:42 | 2024-05-24 13:35:44 |
Judging History
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'