QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#603449 | #8716. 树 | Zaria | RE | 0ms | 17472kb | C++14 | 2.2kb | 2024-10-01 16:37:22 | 2024-10-01 16:37:23 |
Judging History
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...