绝世好题

· · 题解

神题，笔者并没有找到除官解外的题解，也并没有找到任何有人通过本题的证据（不过似乎是 2015 集训队作业），就来记录一下官方题解神仙做法，给个证明。

首先你发现有解答案上界是 2^nn，暴力模拟状态 S 和 u（代表当前每个点经过的奇偶性和当前在那个点）即可。

然后？你不会了看了眼 tag 折半搜索，你尝试把点分成两部分，对两边预处理当前部分状态为 S，在点 u，走到另外一部分时的 S' 和 u'，但你发现你的状态数是没有变化的，似乎还是 2^nn 的。

接下来就是很厉害的想法了。

官解告诉我们保留所有边，直接建反图从 n bfs 给每个点标记一个 dep，把没有 bfs 到的扔掉（显然走到那些点不可能有解），然后把 dep 较小的那一半分到一个集合 B，剩下的分到另外一个集合 A。

它告诉我们只用预处理 A 集合内从状态为 S，在点 u，走到另外一部分时的 S' 和 u'，在 A 时利用这个东西加速跳，在 B 时暴力跳就是正确的，在到达 n 前是不会出现重复的 B 集合奇偶状态的（如果跳到了那些没有 bfs 的点就无解）！

很反直觉不是吗？

然而官解并没有给出证明，这里我们证明一下。

考虑我现在 B 集合跳跃状态为 S，在 B 中某个点 u，我现在想要转一圈后 B 状态仍然是 S。那么说明我从现在起 u 的两条边都会走过（现在会走某条边，之后为了消除本次的奇偶翻转还会再走一次），由于它的 dep_u 是由它的两条出边指向的点更新的，说明它在重复状态前必然会访问到一个 dep_u-1 的点，由于我们是把 dep 小的分 B 内，这个点必然是 B 内的，继续从 dep_u-1 的点出发考虑，我们就发现必然会经过 dep_u-2,dep_u-3,... 的点，也就是必然会经过点 n！

所以我们在 B 跳的次数是不超过 2^{|B|} 次的（官解只给到了 2^{|B|}|B|，笔者认为是不可能 S 一样，u 不同的，上述证明已经说明了这一点，如果笔者给的上界有误请指出），而 A 状态数是 2^{|A|}{|A|} 的，所以 |B| 取 22 左右跑得最快。

参考代码：

#include<bits/stdc++.h>
#define ll long long
#define INF 214748364719260817ll
using namespace std;
ll t,n;
ll l[45],r[45];
ll to[45],td[45];
ll dep[45];
vector<ll>bk[45];
vector<ll>a,b;
struct px
{
    ll nS,nu,c;
};
px dp[1<<18][18];
bool vis[1<<18][18];
px dfs(ll S,ll u)
{
    if(to[u]!=1)return (px){S,u,0};
    if(vis[S][td[u]])return dp[S][td[u]];
    vis[S][td[u]]=1;
    ll nu=u;
    if((S>>td[u])&1)nu=r[u];
    else nu=l[u];
    dp[S][td[u]]=dfs(S^(1<<td[u]),nu);
    ++dp[S][td[u]].c;
    return dp[S][td[u]];
}
ll get_ans(ll aS,ll bS,ll u)
{
    if(u==n-1)return 0;
    if(!to[u])return -INF;
    if(to[u]==1)
        return dp[aS][td[u]].c+get_ans(dp[aS][td[u]].nS,bS,dp[aS][td[u]].nu);
    else
    {
        ll nu=u;
        if((bS>>td[u])&1)nu=r[u];
        else nu=l[u];
        return 1+get_ans(aS,bS^(1<<td[u]),nu);
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    for(ll sb=1;sb<=t;++sb)
    {
        cin>>n;
        memset(to,0,sizeof(to));
        memset(dep,0,sizeof(dep));
        memset(vis,0,sizeof(vis));
        a.clear();b.clear();
        for(ll i=0;i<n;++i)bk[i].clear();
        for(ll i=0;i<n-1;++i)cin>>l[i]>>r[i],--l[i],--r[i];
        for(ll i=0;i<n-1;++i)bk[l[i]].emplace_back(i),bk[r[i]].emplace_back(i);
        queue<ll>q;
        q.emplace(n-1);
        dep[n-1]=1;
        while(!q.empty())
        {
            ll id=q.front();q.pop();
            a.emplace_back(id);
            for(auto it:bk[id])
            {
                if(!dep[it])
                dep[it]=dep[id]+1,q.emplace(it);
            }
        }
        cout<<"Case #"<<sb<<": ";
        if(a.size()<2||!dep[0])
        {
            cout<<"Infinity\n";continue;
        }
        ll where=a.size()/2;
        for(ll i=a.size()-1;i>=max(22ll,where);--i)b.emplace_back(a.back()),a.pop_back();
        swap(a,b);
        ll cot=0;
        for(auto it:a)to[it]=1,td[it]=cot++;
        cot=0;
        for(auto it:b)to[it]=2,td[it]=cot++;
        for(ll i=0;i<(1<<a.size());++i)
            for(ll j=0;j<a.size();++j)
                if(!vis[i][j])
                    dfs(i,a[j]);
        ll res=get_ans(0,0,0);
        if(res<0)cout<<"Infinity\n";
        else cout<<res<<'\n';
    }
}