CF1118F2 Tree Cutting(Hard Version)

Posted by

https://codeforces.com/contest/1118/problem/F2 思路:先dfs求出每个点的深度及其父亲节点。 然后把相同颜色的点加入一个优先队列中,设现在有一个点x,颜色为w。 把离x最远的相同颜色的点与x之间(包括两头)的路径上无颜色的点标上颜色w。 在往上跳的过程中,若发现一个点的颜色已经有颜色了,且这个颜色不为当前颜色,则显然无法完全的分离两种颜色,即无解。最终记录一下颜色为w的深度最低的点lca[w]。 然后建新图。建新图的意义是,把可以对答案有贡献的边连上。对于颜色相同的点,若都无颜色,则将两个点进行连边;否则不管。因为对于相同颜色的点,显然之间的边不能切割。对于两个点其中一个点无颜色一个点颜色为w的情况,将这个点与lca[w]连边。否则将两个颜色不同的点lca[w1],lca[w2]相连。 因为连上的点是lca[w],所以可以大大缩小图的规模。因为相同颜色的点之间不能断边,所以其lca[w]到任意一个颜色为w的点之间的“链”不能断开。就相当于是把颜色相同的点进行“缩点”。 接下来就是dp过程。 设状态转移方程f[x][2],其中f[x][0]表示以x为根节点的子树中(包括根节点)存在无颜色节点时的方案数,f[x][1]表示以x为根节点的子树中(包括根节点)存在有颜色节点时的方案数。 对于初值的设定: No.1

    \[ f[x][0]=(a[x]==0) \]

No.2

    \[ f[x][1]=(a[x]!=0) \]

则:

    \[ f[x][1] = \sum \limits_{k \in g(x)} \prod \limits_{to \in g(x), to \ne k} f[k][1] \cdot (f[to][0] + f[to][1]) \]

且:

    \[ f[x][0] = \prod \limits_{to \in g(x)} (f[to][0] + f[to][1]) \]

代码:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
typedef long long ll;
static const int MAXN=300050;
static const int mod=998244353;
using namespace std;
priority_queue<pair<ll,ll> > q[MAXN];
vector<pair<ll,ll> > Edge;
struct node{
    int to,nextt;
}edge[MAXN<<1];
int n,k,u,v,num,lca[MAXN],a[MAXN],head[MAXN],fa[MAXN],dep[MAXN];
ll f[MAXN][2];
inline int read(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline void addedge(int u,int v){
    edge[++num].to=v;
    edge[num].nextt=head[u];
    head[u]=num;
}
void init(){
    memset(head,0,sizeof(head));
    num=0;
}
void dfs1(int x,int from,int depth){
    fa[x]=from;
    dep[x]=depth;
    for(int i=head[x];i;i=edge[i].nextt){
        int to=edge[i].to;
        if(to==from) continue;
        dfs1(to,x,depth+1);
    }
}
void solve(int x,int from){
    f[x][0]=(a[x]==0);f[x][1]=(a[x]!=0);
    for(int i=head[x];i;i=edge[i].nextt){
        int to=edge[i].to;
        if(to==from) continue;
        solve(to,x);
        f[x][1]=((f[x][0]*f[to][1])%mod+(f[x][1]*(f[to][0]+f[to][1]))%mod)%mod;
        f[x][0]=(f[x][0]*(f[to][0]+f[to][1]))%mod;
    }
}
int main(){
    n=read();k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<n;i++){
        u=read();v=read();
        Edge.push_back(make_pair(u,v));
        addedge(u,v);addedge(v,u);
    }
    dfs1(1,0,1);
    for(int i=1;i<=n;i++) q[a[i]].push(make_pair(dep[i],i));
    for(int i=1;i<=k;i++){
        while(q[i].size()>1){
            int now=q[i].top().second;q[i].pop();
            if(a[fa[now]]&&a[fa[now]]!=i) return 0&printf("0\n");
            else if(!a[fa[now]]) a[fa[now]]=i,q[i].push(make_pair(dep[fa[now]],fa[now]));
        }
        lca[i]=q[i].top().second;
    }
    init();
    for(int i=0;i<(int)Edge.size();i++){
        u=Edge[i].first;v=Edge[i].second;
        if(a[u]==a[v]){
            if(a[u]) continue;
            addedge(u,v);addedge(v,u);
        }
        else if(!a[u]||!a[v]){
            if(!a[u]) swap(u,v);
            addedge(lca[a[u]],v);addedge(v,lca[a[u]]);
        }
        else addedge(lca[a[u]],lca[a[v]]),addedge(lca[a[v]],lca[a[u]]);
    }
    solve(1,0);
    printf("%I64d\n",f[1][1]);
    return 0;
}
]]>

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注