hihocoder 1490 Tree Restoration

构造。

从最后一层开始往上构造。最后一层肯定都是叶子结点，距离为2的肯定是同一个父亲，确定好了父亲之后，可以确定上一层每个节点之间的距离，以及上一层每个节点到还未确定的叶子节点之间的距离。

#include<bits/stdc++.h>

using namespace std;

int n,m,k;

vector<int>v[];

int A[],L[],h[];

int D[][];

int f[];

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<=m;i++) scanf("%d",&A[i]);

    for(int i=;i<=m;i++)

    {

        while(A[i]--)

        {

            int x; scanf("%d",&x);

            v[i].push_back(x);

        }

    }

    for(int i=;i<=k;i++) scanf("%d",&L[i]),h[L[i]]=;

    for(int i=;i<=k;i++) for(int j=;j<=k;j++) scanf("%d",&D[L[i]][L[j]]);

    for(int i=m;i>=;i--)

    {

        int last = ;

        int now = ;

        while()

        {

            if(now==v[i].size()) break;

            while()

            {

                if(h[v[i-][last]]==) last++;

                else break;

            }

            f[v[i][now]] = v[i-][last]; now++;

            while()

            {

                if(now==v[i].size()) break;

                if(D[v[i][now]][v[i][now-]]!=) {last++; break;}

                f[v[i][now]] = v[i-][last]; now++;

            }

        }

        for(int j=;j<v[i].size();j++)

            for(int t=;t<v[i].size();t++)

                D[f[v[i][j]]][f[v[i][t]]]=D[v[i][j]][v[i][t]]-;

        for(int j=;j<v[i].size();j++)

            for(int t=;t<=k;t++)

                D[f[v[i][j]]][L[t]]=D[L[t]][f[v[i][j]]]=D[v[i][j]][L[t]]-;

    }

    for(int i=;i<=n;i++)

    {

        printf("%d",f[i]);

        if(i<n) printf(" ");

        else printf("\n");

    }

    return ;

}