A simple Blog for wyx I've been down the bottle hoping.
BZOJ 3696 化合物 树形$dp$
发表于: | 分类: Oi | 评论:0 | 阅读:116

想看真正的正解的孩子可以现在就关闭窗口了……
正解我不会,我只会$O(nh^2)$的暴力
我们还是来说暴力算法吧$OVO$
我们枚举每一个点
讨论以$x$为$LCA$在以他为根的子树中对答案的贡献
假设已经合并了前$c-1$个子树,讨论第$c$个子树
假设在前$c-1$个子树中有$x1$个距离$x$为$a1$,有$x2$个距离$x$为$a2$,那么对答案的贡献就是
$$(a1\quad xor\quad a2)· x1 · x2$$
一边合并一边更新答案就行
时间复杂度$O(nh^2)$
正解是$FWT$,表示多项式根本不会的我当时就跪了,不过好像暴力跑的飞快……可能真的不太好卡吧
对了,注意从子树合并过来的时候距离$+1$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 100000+5
#define M N
using namespace std;

int head[N];

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct graph
{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y);
    head[x] = cnt;
}

int a[N][500+5];
int len[N];
int ans[N];

void DFS(int x)
{
    a[x][0] = 1;
    for(int i=head[x];i;i=edge[i].next)
    {
        DFS(edge[i].to);
        for(int j=0;j<=len[x];++j)
            for(int k=0;k<=len[edge[i].to];++k)
                ans[j^(k+1)] += a[x][j] * a[edge[i].to][k];
        len[x] = max(len[x],len[edge[i].to]+1);
        for(int j=0;j<=len[edge[i].to];++j)
            a[x][j+1] += a[edge[i].to][j];
    }
}

int main()
{
    int n = read();
    register int i=2;
    for(int tmp;i<=n;++i)
        tmp = read(),add(tmp,i);
    DFS(1);
    i = 0;
    while(1)
        if(ans[i])
            printf("%d\n",ans[i++]);
        else
            break;
    
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP