时间下不去了
查看原帖
时间下不去了
1002446
BHIS_oldsix楼主2024/11/7 16:10
#include<iostream>
#include<cmath>
using namespace std;
int m,n;
struct EDGE{
    int to,next;
}edge[200005];
int cnt[20005],now,fa[20005],c[20005],dp[20005][5];// 1 no 2 white 3 black
int colour(int s){
    if(s==0)
        return 3;
    if(s==1)
        return 2;
    return 1;
}
inline void addd(int A,int B){
    now++;
    edge[now].to=B;
    edge[now].next=cnt[A];
    cnt[A]=now;
    now++;
    edge[now].to=A;
    edge[now].next=cnt[B];
    cnt[B]=now;
}
inline void dfs(int s){
    for(int i=cnt[s];i;i=edge[i].next){
        if(edge[i].to==fa[s])continue;
        fa[edge[i].to]=s;
        dfs(edge[i].to);
    }
}
inline void work(int s){
    for(int i=cnt[s];i;i=edge[i].next){
        if(edge[i].to==fa[s])continue;
        work(edge[i].to);
    }
    if(s<=n)return;
    for(int i=cnt[s];i;i=edge[i].next){
        if(dp[edge[i].to][2]-1<=dp[edge[i].to][3] and dp[edge[i].to][2])
            dp[s][2]+=dp[edge[i].to][2]-1;
        else
            dp[s][2]+=dp[edge[i].to][3];
             
        if(dp[edge[i].to][3]-1<=dp[edge[i].to][2] and dp[edge[i].to][3])
            dp[s][3]+=dp[edge[i].to][3]-1;
        else
            dp[s][3]+=dp[edge[i].to][2];
    }
    dp[s][2]++;
    dp[s][3]++;
}
inline int read(){
    int x=0,f=0;char c=getchar();
    for(;c<'0'||c>'9';c=getchar()){
        while(c=='-'){
            f=1;
            break;
        }
    }
    for(;c>='0'&& c<='9';c=getchar()){
        x=(x<<1)+(x<<3)+(c^'0');
    }
    return f ? -x : x;
}
int main(){
    //freopen("add8.in","r",stdin);
    //scanf("%d %d",&m,&n);
    m=read();
    n=read();
    for(int i=1;i<=n;i++){
        //scanf("%d",&c[i]);
        c[i]=read();
        dp[i][colour(c[i])]=1;
    }
    for(int i=1,u,v;i< m;i++){
        //scanf("%d %d",&u,&v);
        u=read();
        v=read();
        addd(u,v);
    }
    dfs(n+1);
    work(n+1);
    printf("%d",min(dp[n+1][2],dp[n+1][3]));
    return 0;
}

想压时间,求

2024/11/7 16:10
加载中...