P4434 题解

· · 题解

一种小常数单 \log 做法。

把 1 定为树根，那么对于每条边，要么是指向父亲（0），要么是指向儿子（1）。

考虑转换 m 条限制：u\rightarrow lca,v\rightarrow lca 的路径上的边分别全 0、全 1 或分别全 1 全 0。

我们记一个点 u （1<u\le n）的点权表示指向 u 的边的状态（0/1），则可以得到两条限制（son_u 表示 lca 往 u 跳一步走到的点，son_v 同理）：

那么对于限制 1,2，每次合并树上的一条祖先链，连通块内相同。

对于考虑限制 3，若 u,v 已经在一个联通块，则矛盾，输出 0；否则连接 u,v 所在的联通块。

把连通块缩点，得到一个无向图，则有解必须满足该图可以黑白染色。那直接建出来然后 dfs 一遍就好了。若有解则答案即为 2 的新图的连通块数量次方，因为若联通的点确定，则可以确定；否则不会被确定。

后面的两个操作用并查集复杂度 O(n\alpha(n))，问题就是合并一条树链。

考虑给链上除了顶点的点打上一个标记，若一个点超过一个标记，则将它和它的父亲合并。树上差分 + 并查集即可，复杂度 O(n\alpha(n))。

于是瓶颈在求 lca，精细实现可以优化到 O(n)。我写的是树剖 lca，总复杂度 O(n\log n)。

常数非常小，加上快读可以直接拿到（目前的）最优解。

const int N=3e5+5,MOD=1e9+7;
int n,m,u[N],v[N];
const int E=N<<1;
int tot=0,head[N],to[E],nxt[E];
inline void Add(int u,int v){to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}

int f[N];                                   // 并查集
inline void init(){for(int i=1;i<=n;i++)f[i]=i;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
inline void merge(int u,int v){u=find(u);v=find(v);if(u^v)f[u]=v;}

int fa[N],dep[N],siz[N],son[N],top[N];      // 树剖
void dfs1(int u,int fath){
    fa[u]=fath;dep[u]=dep[fath]+1;siz[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];if(v==fath)continue;
        dfs1(v,u);siz[u]+=siz[v];(siz[v]>siz[son[u]])&&(son[u]=v);
    }
}
void dfs2(int u,int tp){
    top[u]=tp;if(!son[u])return;dfs2(son[u],tp);
    for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v^son[u]&&v^fa[u])dfs2(v,v);}
}
inline int LCA(int u,int v){for(;top[u]^top[v];u=fa[top[u]])if(dep[top[u]]<dep[top[v]])swap(u,v);return dep[u]<dep[v]?u:v;}
inline int gson(int u,int v){
    int lst=0;
    for(;top[v]^top[u];v=fa[top[v]])lst=top[v];
    return u==v?lst:son[u];
}

bool vis[N],col[N];
void dfs(int u){                            // 黑白染色
    vis[u]=true;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];if(vis[v]){if(col[u]==col[v]){puts("0");exit(0);};continue;}
        col[v]=!col[u];dfs(v);
    }
}
bool fl[N];int d[N];
void dfs(int u,int fath){
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];if(v==fath)continue;
        dfs(v,u);d[u]+=d[v];
    }
    if(d[u])merge(fath,u);                  // 若有标记则合并
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<n;i++){scanf("%d%d",&u,&v);Add(u,v);Add(v,u);}
    dfs1(1,0);dfs2(1,1);init();
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u[i],&v[i]);
        int l=LCA(u[i],v[i]);
        if(u[i]^l){d[u[i]]++;d[gson(l,u[i])]--;}
        if(v[i]^l){d[v[i]]++;d[gson(l,v[i])]--;}
        if(u[i]==l||v[i]==l){fl[i]=true;continue;}// 注意特判 lca=u 或 lca=v 的情况
    }
    dfs(1,0);
    tot=0;memset(head,0,sizeof head);
    for(int i=1;i<=m;i++){
        u[i]=find(u[i]);v[i]=find(v[i]);
        if(fl[i])continue;
        if(u[i]^v[i]){Add(u[i],v[i]);Add(v[i],u[i]);}
        else{puts("0");return 0;}           // 若有 u,v 不同的限制，u,v 却在一个块内
    }
    int res=1;
    for(int i=2;i<=n;i++)if(f[i]==i&&!vis[i]){
        dfs(i);res=(res<<1)%MOD;            // 找到一个联通块，答案乘2
    }
    printf("%d\n",res);
    return 0;
}