8 VC Venture Cup 2016-Final Round D.Prorder Test 2分樹形dp

Prorder Test
テーマ接続:
http://www.codeforces.com/contest/627/problem/D
Description
For his computer science class、Jacob builds a model tree with sticks and balls containing n nodes in the shpe of a tree.Jacob has spent ai minutes building the i-th ball in the tree.
Jacob's teacher will evaluate his model and grade Jacob based on the effort he has put in.However，she does not have enough time to search his whole tree to determine this；Jacob knows that she will exmine the first k nodes in a DFS-order trversal of the tree.She will then assign Jacob a grade to the minimum ai she finds among those k nodes.
Though Jacob does not have enough time to rebuild his model、he can chose the root node that his teacher starts from.Frthere、he can rerange the list of neigh bors of herech node in the fider.Hearth the fiders.heregs.Hearth.Hearth.Hearth the.Herthers.Hearth。
A DFS-order trversal is＿ordeng of the nodes of a rooted tree，built by a recursive DFS-procedure initially caled on the root of the tree.When caled on a given node v，the procedues does the follwing:
Print v.Traverse the list of neighbors of the node v in order and iterabiely call DFS-procedure on each one.Do not call DFS-procedure on node u if You came to node v directly from.
Input
The first line of the input contains two positive integers，n and k(2̵≦𔎅n𔎅n≦200𔎅000，1𔎅≦󈙕k̵̵̵̵̵̵̵󈙕̵̵̵̵̵̵the n))))-thellbers bersbers bers
The second line contains n integers、ai(1̵≦𔎅ai̵≦𔎅1𔎅1𔎅000)、the time Jacob used to build the i-th ball.
Each of the next n̵-𔎅1 line s contains two integers ui、vi(1̵≦𔎅ui、̵vi̵𔎅n、ui󈙕vi)present Jallect.ine。
Output
Print a single integer-the maximum grade Jacob can get by picking the right root of the tree and rearing the list of neigh bors.
Sample Input
5 3 3 6 1 4 1 1 2 2 4 5 1 3
Sample Output
3
ベント
題意
木をあげます。
dfs検索の順序は、少なくともk個の点より大きく、そしてこのk個の点の最小値が最大です。
クイズ:
二点の答えをチェックします。
私たちはmidより大きい点を1と表記します。
そして私たちは木dpを始めることができます。
明らかにある点については、息子の木を除いてすべての点が条件を満たしています。そうでないと、息子二人の不完全な子樹を選ぶことができます。
そして私たちはこれを通じてdpを行えばいいです。最大値と大きい値を記録します。
そうだ、彼の父親をチェックして、この点が上に伸びるかどうか見てください。
コード

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
int n,k;
int a[maxn],w[maxn],sz[maxn],up[maxn],dp[maxn];
vector<int> E[maxn];
int flag = 1;
void dfs(int x,int fa,int m)
{
    sz[x]=1;
    for(int i=0;i<E[x].size();i++)
    {
        int v = E[x][i];
        if(v==fa)continue;
        dfs(v,x,m);
        w[x]+=w[v];
        sz[x]+=sz[v];
    }
}
void solve(int x,int fa,int m)
{
    int Max1=0,Max2=0,tot=0;
    for(int i=0;i<E[x].size();i++)
    {
        int v=E[x][i];
        if(v==fa)continue;
        if(w[x]-w[v]==sz[x]-sz[v]&&up[x])up[v]=1;
        solve(v,x,m);
        if(a[v]<m)continue;
        if(sz[v]==w[v])tot+=sz[v];
        else
        {
            if(dp[v]>Max1)Max2=Max1,Max1=dp[v];
            else if(dp[v]>Max2)Max2=dp[v];
        }
    }
    if(a[x]<m)return;
    if(tot+Max1+Max2+up[x]*(n-sz[x])+1>=k)flag=1;
    dp[x]=tot+Max1+1;
}
int check(int x)
{
    for(int i=1;i<=n;i++)
        dp[i]=0,up[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=x)
            w[i]=1;
        else
            w[i]=0;
    }
    flag = 0;
    dfs(1,-1,x);
    up[1]=w[1];
    solve(1,-1,x);
    return flag;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        E[x].push_back(y);
        E[y].push_back(x);
    }
    int l = 0,r = 1e6+5,ans = 1e6+5;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(check(mid))l=mid+1,ans=mid;
        else r=mid-1;
    }
    cout<<ans<<endl;
}
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int n,m,t,i,x[11][11];
int mo=10007;
void multiply(int a[11][11],int b[11][11])
{
    int i,j,k,c[11][11];
    for (i=0;i<=t;i++)
        for (j=0;j<=t;j++)
        {
            c[i][j]=0;
            for (k=0;k<=t;k++) c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mo;
        }

    for (i=0;i<=t;i++)
        for (j=0;j<=t;j++) 
            a[i][j]=c[i][j];
}
void binary(int x[11][11],int a)
{
    int i,j,y[11][11];
    if (a==1) return;
    for (i=0;i<=t;i++)
        for (j=0;j<=t;j++) 
            y[i][j]=x[i][j];
    multiply(x,x);
    binary(x,a/2);
    if (a%2==1) multiply(x,y);
}
int main()
{
    scanf("%d%d%d",&m,&n,&t);
    for (i=0;i<=t;i++)
    {
        if (i!=0) x[i-1][i]=t-i+1;
        x[i][i]=m-t;
        if (i!=t) x[i+1][i]=i+1;
    }
    binary(x,n);
    printf("%d
",x[0][0]);
}