CF231E 题解

本文采用 CC BY-NC-SA 4.0 协议发布。

前言

提供一个圆方树做法。

孩子圆方树学傻了，忘了还有缩点这回事。

正文

建圆方树。

考虑一条圆方树上的路径，哪些点对答案有贡献：

• 方点，这表示路径经过一个环，方案数 \(\times 2\).

• 旁边有方点的圆点。这表示走到这时可以选择在环上绕一圈，方案数 \(\times 2\).

于是设“旁边有方点的圆点”权值为 \(2\)，方点权值为 \(\dfrac{1}{2}\)，其他点权值 \(1\)，路径上的点权值乘起来就是方案数。取对数后转化为路径权值和问题。

代码

#include <iostream>
#include <cassert>
#include <vector>
#include <stack>
#define UP(i,s,e) for(auto i=s; i<e; ++i)
using std::cin; using std::cout;
namespace m{ // }{{{
constexpr int N = 1e5, M = 1e5, lgN = 17, MOD = 1e9+7;
int in, im;
std::vector<int> tos0[N], tos1[N*2];
int pntcnt, low[N], dfn[N]; //nearsq[N];
extern int treesum[];
std::stack<int> vising;
void tarjan_dfs(int x, int f){
    static int dfstim = 0;
    dfstim++;
    low[x] = dfn[x] = dfstim;
    vising.push(x);
    for(int i:tos0[x]){
        if(i == f) continue;
        if(dfn[i]){
            low[x] = std::min(low[x], dfn[i]);
            continue;
        }
        tarjan_dfs(i, x);
        low[x] = std::min(low[x], low[i]);
        if(low[i] > dfn[x]){
            assert(vising.top() == i);
            tos1[i].push_back(x);
            tos1[x].push_back(i);
            //while(vising.top() != i){
            //    vising.pop();
            //}
            vising.pop();
        } else if(low[i] == dfn[x]){
            while(1){
                int t = vising.top(); vising.pop();
                tos1[pntcnt].push_back(t);
                tos1[t].push_back(pntcnt);
                treesum[t] = 1;
                if(t == i) break;
            }
            tos1[pntcnt].push_back(x);
            tos1[x].push_back(pntcnt);
            treesum[x] = 1;
            //nearsq[x] = pntcnt;
            pntcnt++;
        }
    }
}
int dfn1[N*2], fa[N*2], treesum[N*2], st[lgN][N*2];
void dfs_mark(int x, int f){
    static int dfstim = -1; dfstim++;
    fa[x] = f; treesum[x] += (x==f ? 0 : treesum[f]) - (x>=in);
    dfn1[x] = dfstim;
    st[0][dfn1[x]] = fa[x];
    for(int i:tos1[x]){
        if(i == f) continue;
        dfs_mark(i, x);
    }
}
int dfnmin(int x, int y){ return dfn1[x] < dfn1[y] ? x : y; }
int pow2[N];
void prepare(){
    cin >> in >> im;
    pntcnt = in;
    UP(i, 0, im){
        int ia, ib; cin >> ia >> ib; ia--, ib--;
        tos0[ia].push_back(ib);
        tos0[ib].push_back(ia);
    }
    tarjan_dfs(0, 0);
    dfs_mark(0, 0);
    UP(layer, 1, lgN){
        UP(i, 0, pntcnt-(1<<layer)+1){
            st[layer][i] = dfnmin(st[layer-1][i], st[layer-1][i+(1<<layer>>1)]);
        }
    }
    pow2[0] = 1;
    UP(i, 1, pntcnt-in+1){
        pow2[i] = pow2[i-1] * 2 % MOD;
    }
}
int getlca(int x, int y){
    if(x == y) return x;
    x = dfn1[x]; y = dfn1[y];
    if(x > y) std::swap(x, y);
    int delta = std::__lg(y-x);
    return dfnmin(st[delta][x+1], st[delta][y-(1<<delta)+1]);
}
void work(){
    int ix, iy; cin >> ix >> iy; ix--, iy--;
    //if(nearsq[ix]) ix = nearsq[ix];
    //if(nearsq[iy]) iy = nearsq[iy];
    int lca = getlca(ix, iy);
    int sum = treesum[ix] + treesum[iy] - treesum[lca] - (lca ? treesum[fa[lca]] : 0);
    cout << pow2[sum] << '\n';
}
} // {}}}
int main(){ 
    m::prepare();
    int iq;
    cin >> iq;
    while(iq--) m::work();
}