BZOJ1063 도로 설계

팁: 1.이것은 나무입니다.나무 사슬이 경변logn에 대한 증명을 분할한 것을 기억하십니까? 이 문제에 대해 어떤 시사점이 있습니까?
아이디어는 여러분에게 남겨두고 코드 뒤에 저는 두 가지 방법에 대해 상세하게 설명할 것입니다.
No.1 :

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 110000;
__inline int re() { int n; scanf("%d" , &n); return n; }

ll  n , m , modu;
vector<int> g[maxn];
ll  d[maxn][15][3];
int c[maxn][15][3];

bool dp(int u , int m , int fa)
{
    d[u][m][0] = 1;
    c[u][m][0] = 1;
    d[u][m][1] = d[u][m][2] = 0;

    if(g[u].size()==1 && g[u][0]==fa) return true;

    for(int i=0;i<g[u].size();i++)
    {
        int v = g[u][i];
        if(v == fa) continue;
        dp(v , m , u);

        ll f = (d[v][m-1][0] + d[v][m-1][1] + d[v][m-1][2])%modu;
        ll r = (d[v][m][0]+d[v][m][1])%modu;

        bool p = (c[v][m-1][0] | c[v][m-1][1] | c[v][m-1][2]);
        bool k = (c[v][m][0] | c[v][m][1]);


        d[u][m][2] = (d[u][m][2]*f + d[u][m][1]*r)%modu;
        c[u][m][2] = (c[u][m][2]&p) | (c[u][m][1]&k);

        d[u][m][1] = (d[u][m][1]*f + d[u][m][0]*r)%modu;
        c[u][m][1] = (c[u][m][1]&p) | (c[u][m][0]&k);

        d[u][m][0] = (d[u][m][0] * f)%modu;    c[u][m][0] &= p;
    }
    return c[u][m][0] || c[u][m][1] || c[u][m][2];
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    #endif
    n = re(); m = re(); scanf("%lld" , &modu);

    if(m!=n-1) { puts("-1
-1"); return 0; }
    while(m--)
    {
        int a = re() , b = re();
        g[a].push_back(b);
        g[b].push_back(a);
    }


    for(int i=1;;i++) if(dp(1 , i , -1)) { printf("%d
%lld
" , i-1 , (d[1][i][0]+d[1][i][1]+d[1][i][2])%modu); break; }

    return 0;
}

No.2 :

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 110000;
__inline int re() { int n; scanf("%d" , &n); return n; }

ll  n , m , modu;
vector<int> g[maxn];

int ch[maxn][2];
ll d[15][maxn][3];
int c[15][maxn][3];
int v[15][maxn][3];

void dfs(int u , int F)
{
    int last = 0;
    for(int i=0;i<g[u].size();i++)
    {
        int v = g[u][i];
        if(v==F) continue;
        ch[u][0] = v;
        ch[v][1] = last;
        last = v;
        dfs(v , u);
    }
}


void tangent(ll& a , ll b) { a = (a+b)%modu; }

ll dp(int m , int u , int l)
{
    ll& res = d[m][u][l];
    int& b = c[m][u][l];

    if(v[m][u][l]) return res;
    v[m][u][l] = 1;

    if(!u) { b = (m>=0 && !l); return res = (m>=0 && !l); }

    int b1 = 0 , b2 = 0;
    if(l) 
    {
        ll s = 0;
        for(int i=0;i<2;i++) tangent(s , dp(m , ch[u][0] , i)) , b1 |= c[m][ch[u][0]][i];
        res = (s*dp(m , ch[u][1] , l-1))%modu; b1 &= c[m][ch[u][1]][l-1];
    }
    if(m)
    {
        ll s = 0;
        for(int i=0;i<3;i++) tangent(s , dp(m-1 , ch[u][0] , i)) , b2 |= c[m-1][ch[u][0]][i];
        s = (s * dp(m , ch[u][1] , l ))%modu , b2 &= c[m][ch[u][1]][l];
        res = (res + s)%modu;
    }

    b = b1 | b2;
    return res;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    #endif
    n = re(); m = re(); scanf("%lld" , &modu);

    if(m!=n-1) { puts("-1
-1"); return 0; }
    while(m--)
    {
        int a = re() , b = re();
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1 , -1);

    for(int i=1;;i++) if(dp(i , 1 , 0) || c[i][1][0]) { printf("%d
%lld
" , i-1 , d[i][1][0]); break; }
    return 0;
}

이 문제는 트리 DP입니다. 트리 체인을 분석한 증명에 의하면 체인의 수가 logn개보다 많을 수 없기 때문에 우리는 첫 번째 질문에서 구한 답안을 일일이 열거할 수 있습니다. 만약에 지금이 가능하다면 반드시 가장 작은 것입니다.또 하나 무시되는 이유는 체인 수를 일일이 열거하지 않으면 DP를 할 수 없기 때문이다. 전체적으로 가장 좋은 상태가 국부적으로 가장 좋은 것을 요구하지 않기 때문이다.
첫 번째 방법은 인터넷에서 비교적 유행하는 것으로 여기서 상태를 다음과 같이 표시할 수 있다.
f[i][j][k]→번호가 i의 결점으로 최대 체인 깊이(즉 이때의 답안)가 j를 초과하지 않고 k개의 체인을 아래로 연결할 때의 방안 수입니다.(단, 두 코드의 하표 순서가 다르다는 것을 주의한다.)
그렇다면 대표의 의미에 따라 옮기는 것은 어렵지 않다.
우리
Tu=∑0≤k≤2f[u][j-3-1][k]Gu=∑0≤k≤1f[u][j][k]그러면 다음과 같습니다.
f[i][j][0]=∏u∈sonsTu
f[i][j][1]=∑u∈sonsGu×∏v∈sons,v≠uTv
f[i][j][2]=∑u∈sons∑v∈sons,v≠u⎛⎝Gu×Gv×∏k∈sons,k≠u,k≠vTv⎞⎠
이 식은 구하기 매우 어렵기 때문에 구법을 최적화시켜야 한다.각 결점의 아들 간에 가방 DP를 실시하여 선형성을 최적화하는 것을 고려할 수 있다.즉 현재의 f[i][j][]로 서로 영향을 미친다.이것은 사실 이해하기 어렵지 않다.
다음은 이 문제의 또 다른 실현 방법을 이야기하자. 왼쪽 아들과 오른쪽 형제는 나무 한 그루를 나타낸다. 여기는 이런 표현 형식을 많이 말하지 않고 우리는 상태를 직접 본다.
f[i][j][k]→결점 i에 대해 이때 그 체인의 깊이(바로 이때 i를 근본으로 하는 답안)는 j이고 i세대 결점은 k개의 체인을 연결할 수 있는 방안수이다.
세대 결점이 무엇인지 설명해 보자. 왼쪽 아들 오른쪽 형제의 표현법은 원래 그림의 부자 관계를 나타낼 수 없기 때문에 우리는 원도에서 같은 아버지의 결점을 세대 결점이라고 부른다.
매번의 결정은 결점 i가 자신의 아버지와 연결되었는지 토론한 다음에 자신의 아들들이 자신과 몇 개의 연결을 해야 하는지를 결정하는 것이다.아버지 결점, 임무 분배, 아들 결점들이 임무를 점차적으로 수행하는 것 같아.
각 의사 결정에 대해 다음과 같이 모서리와 모서리를 연결하지 않는 전환 방정식이 적용됩니다.
G1=∑0≤i≤1f[leftSon][j][i]∗f[rightSon][j][k−1]
G2=∑0≤i≤2f[leftSon][j−1][i]∗f[rightSon][j][k]
그렇다면 이때 정답은 G1+G2다.
이렇게 하면 많이 간소화되었다는 것을 알 수 있다. 왼쪽 아들 오른쪽 형제는 일종의 표현 방법이고 이런 표현 방법은DP의 이동을 간소화할 수 있다.이 표현은 DP의 상태를 충분히 적용하기 때문입니다.
마지막으로 주의해야 할 것은 이 문제는 실행 가능한 문제를 판단할 때 이때의 답안이 0인지 직접 볼 수 없기 때문에 나는 하나의 수조로 이때의 타당성을 나타냈다.