[CF891D]Sloth

Description

给出一棵n个节点的树，你需要删去并加入一条边，使得原图仍然是一棵树，并且有完美匹配。

求方案数。

n<=5*1e5

Solution

考虑枚举删去一条边，我们只需要统计某个子树内和外有多少个点可以成为匹配点。

可以设Dp，四种状态，根节点是否被匹配，除根外是否有节点未被匹配。

这样子可以O(n)统计出子树内的答案，但是子树外的答案似乎没有那么好求。

观察我们的转移，是从儿子向父亲合并的，这也限制了我们在换根的时候不能用前缀和来优化。

真的是这样吗？

Orz wxh

我们可以考虑把转移写成一种类似矩阵乘法（当然并不是），使得这个转移满足交换律，并且和谁是父亲无关，只需要把不是父亲的点的trans状态都加起来就是答案。

这个加法是重定义之后的，这样子就可以用前缀和优化换根到O(n)解决问题。

/注释部分是原来的转移/

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a) for(int i=lst[a];i;i=nxt[i])
using namespace std;

typedef long long ll;

int read() {
    char ch;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    int x=ch-'';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x;
}

const int N=e6+;

int t[N<<],nxt[N<<],lst[N],l;
void add(int x,int y) {
    t[++l]=y;nxt[l]=lst[x];lst[x]=l;
}

int n,x,y,size[N],a[N],L[N],R[N],tot;

struct Dp{
    int a[][];
    Dp trans() {
        Dp x;
        x.a[][]=a[][];
        x.a[][]=a[][]+a[][];
        x.a[][]=a[][];
        x.a[][]=a[][];
        return x;
    }
    friend Dp operator + (Dp x, Dp y) {
        Dp z;
        memset(z.a,,sizeof(z.a));
        fo(i,,)
            fo(j,,)
                fo(k,,-i)
                    fo(l,,-j)
                        z.a[i+k][j+l]+=x.a[i][j]*y.a[k][l];
        /*z.a[][]=x.a[][]*y.a[][];

        z.a[][]=x.a[][]*(y.a[][]+y.a[][]);
        z.a[][]+=x.a[][]*y.a[][];

        z.a[][]=x.a[][]*y.a[][];
        z.a[][]+=x.a[][]*y.a[][];

        z.a[][]=x.a[][]*y.a[][];
        z.a[][]+=x.a[][]*y.a[][];
        z.a[][]+=x.a[][]*(y.a[][]+y.a[][]);
        z.a[][]+=x.a[][]*y.a[][];*/

        return z;
    }
}f[N],g[N],pre[N],Null;

void dfs(int x,int y) {
    rep(i,x) if (t[i]!=y) dfs(t[i],x);
    f[x]=Null;size[x]=1;
    rep(i,x)
        if (t[i]!=y) {
            size[x]+=size[t[i]];
            f[x]=f[x]+f[t[i]].trans();
        }
}

void dp(int x,int y) {
    L[x]=++tot;
    rep(i,x) if (t[i]!=y) a[++tot]=t[i];
    R[x]=tot;

    pre[L[x]]=y?g[x].trans():Null;
    fo(i,L[x]+,R[x]) pre[i]=pre[i-]+f[a[i]].trans();

    Dp now=Null;
    fd(i,R[x],L[x]+) {
        g[a[i]]=pre[i-]+now;
        now=now+f[a[i]].trans();
    }

    fo(i,L[x]+,R[x]) dp(a[i],x);
}

int main() {
    n=read();
    fo(i,,n-) {
        x=read();y=read();
        add(x,y);add(y,x);
    }
    Null.a[][]=;
    dfs(,);dp(1,0);
    ll ans=;
    fo(i,,n)
        if (f[i].a[][]==&&g[i].a[][]==) ans+=(ll)size[i]*(n-size[i]);
        else ans+=(ll)(f[i].a[][]+f[i].a[][])*(g[i].a[][]+g[i].a[][]);
    printf("%lld\n",ans);
    return ;
}