【不知道是啥的NOIP模拟赛】网络入侵

题意是这样的：

给你一棵树，每个边有一个初始的0/1边权。你希望把它弄成一个给定的样子。

你每次可以选一条树链取反，然后问你最少要操作几次。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

正常人的想法大概就是，我对一条树链xor->差分。

然后就大力树形dp转移一下，总是能做出来的。

然后这里给出一个牛逼的做法：

首先把已经满足条件的边相连的点全都缩起来，这样就得到了一个新的树。

于是原问题等价于，最少几笔可以把这棵新树画完。

然后数一下多少个奇节点，直接/2就好了。

我们可以发现由于这是一棵树，肯定会有叶子，所以你甚至不用特判=0的情况。

是不是非常强。。。。

（反正这个做法也不是我想出来的，也不是std的做法）

#include<bits/stdc++.h>

#define lson (o<<1)

#define rson (o<<1|1)

#define fi first

#define sc second

#define dbg(x) cout<<#x<<" = "<<(x)<<endl;

typedef long long ll;

typedef unsigned int uint;

typedef unsigned long long ull;

using namespace std;

const double pi=acos(-);

const double eps=1e-;

inline int lowbit(int x){return x&(-x);}

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

template<typename T> inline T max(T x,T y,T z){return max(max(x,y),z);}

template<typename T> inline T min(T x,T y,T z){return min(min(x,y),z);}

template<typename T> inline T sqr(T x){return x*x;}

template<typename T> inline void checkmax(T &x,T y){x=max(x,y);}

template<typename T> inline void checkmin(T &x,T y){x=min(x,y);}

template<typename T> inline void read(T &x){

x=;T f=;char ch;do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

do x=x*+ch-'',ch=getchar();while(ch<=''&&ch>='');x*=f;

}

template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){

    A ans=;

    for(;p;p>>=,x=1LL*x*x%yql)if(p&)ans=1LL*x*ans%yql;

    return ans;

}

struct FastIO{

    static const int S=;

    int wpos;char wbuf[S];

    FastIO():wpos() {}

    inline int xchar(){

        static char buf[S];

        static int len=,pos=;

        if(pos==len)pos=,len=fread(buf,,S,stdin);

        if(pos==len)return -;

        return buf[pos++];

    }

    inline int read(){

        int c=xchar(),x=;

        while(c<=&&~c)c=xchar();

        if(c==-)return -;

        for(;''<=c&&c<='';c=xchar())x=x*+c-'';

        return x;

    }

}io;

//#define read io.read

const int N=;

struct Edge{int u,v,next;}G[N<<],T[N];

int fa[N],vis[N],ind[N],n,ans;

char s[N],p[N];

inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

inline void addedge(int u,int v,int pos){

    int w=s[pos]-'';

    ind[u]+=w;ind[v]+=w;vis[u]=;vis[v]=;

}

inline void merge(int x,int y){

    int xx=find(x),yy=find(y);

    fa[xx]=yy;

}

int main(){

    freopen("intrusion.in","r",stdin);

    freopen("intrusion.out","w",stdout);

    n=read();

    scanf("%s",s+);scanf("%s",p+);

    for(int i=;i<=n;i++)fa[i]=i;

    for(int i=;i<n;i++){

        int u=read(),v=read(),x=s[i]-'',y=p[i]-'';

        if(!y)merge(u,v);

        T[i].u=u;T[i].v=v;

    }

    for(int i=;i<n;i++){

        int xx=find(T[i].u),yy=find(T[i].v);

        if(xx!=yy)addedge(xx,yy,i);

    }

    for(int i=;i<=n;i++)if(vis[i]&&(ind[i]&))ans++;

    printf("%d\n",ans>>);

}

巴特西

【不知道是啥的NOIP模拟赛】网络入侵

最新文章

热门文章