微软2017年预科生计划在线编程笔试 

原题链接：http://hihocoder.com/problemset/problem/1490?sid=1299846 
题目看上去很麻烦，先看样例 
第一行：节点数N，层数M，叶子数K 
第二行：M个数，表示每层的节点数A[I] 
接下来M行，每行A[I]个数，表示该层节点编号B[I][j]（从左到右顺序） 
然后是一行K个数，表示叶子的编号 
最后K×K的矩阵表示叶子间距离D[I][j]
根据两个节点间的距离，可以得知两个节点是否是同一个节点的子节点（距离为1） 
由于给了节点顺序，因此我们只需要贪心地往左面的节点连接子节点即可
因此，问题转换成判断同一层相邻两个节点间的距离是否为2 
如果为2，则接到同一个节点；否则，接到上一层的下一个非叶子节点上
至于距离，可以找到该节点下面的任意一个叶子节点，用这个叶子节点到目标的值减去层数差即可
<pre style="background-color:#fff">#include &lt;cstdio&gt;
#include &lt;cstring&gt;
using namespace std;

#define Log(format, ...) //printf(format, ##__VA_ARGS__)

const int maxn = 105;

int nodeNum[maxn];
int nodeIdx[maxn][maxn];
int leaves[maxn];
bool isLeaf[maxn];
int dis[maxn][maxn];

int parents[maxn];
int child[maxn];
int delta[maxn];

int findAndUpdateLastNode(int &amp;lastNode, int &amp;lastNodeIdx, int deep,
 int nowIdx) {
 // 查找并更新上一层的第一个有孩子的节点
 for (int k = lastNode+1; k &lt; nodeNum[deep - 1]; ++k) {
 if (!isLeaf[nodeIdx[deep - 1][k]]) {
 lastNode = k;
 break;
 }
 }
 lastNodeIdx = nodeIdx[deep - 1][lastNode];

 child[lastNodeIdx] = child[nowIdx];
 delta[lastNodeIdx] = delta[nowIdx] + 1;

 return lastNode;
}

int main() {
 memset(parents, 0, sizeof(parents));
 memset(isLeaf, false, sizeof(isLeaf));
 memset(delta, 0, sizeof(delta));
 memset(parents, 0, sizeof(parents));
 memset(delta, 0, sizeof(delta));

 int N, M, K;
 scanf(&#34;%d%d%d&#34;, &amp;N, &amp;M, &amp;K);
 for (int i = 0; i &lt; M; ++i)
 scanf(&#34;%d&#34;, &amp;nodeNum[i]);
 for (int i = 0; i &lt; M; ++i)
 for (int j = 0; j &lt; nodeNum[i]; ++j)
 scanf(&#34;%d&#34;, &amp;nodeIdx[i][j]);
 for (int i = 0; i &lt; K; ++i) {
 scanf(&#34;%d&#34;, &amp;leaves[i]);
 isLeaf[leaves[i]] = true;
 child[leaves[i]] = i;
 }
 for (int i = 0; i &lt; K; ++i)
 for (int j = 0; j &lt; K; ++j)
 scanf(&#34;%d&#34;, &amp;dis[i][j]);

 Log(&#34;input ok\n&#34;);

 for (int i = M - 1; i &gt; 0; --i) { // 处理第i层
 Log(&#34;\tdepth:%d\n&#34;, i);
 int lastNode = -1;
 int lastNodeIdx = -1;

 for (int j = 0; j &lt; nodeNum[i]; ++j) { // 处理当前层的第j个节点
 int nowIdx = nodeIdx[i][j]; // 当前节点的编号
 Log(&#34;\t\tnowIdx:%d\n&#34;, nowIdx);
 if (lastNode == -1) {
 // 处理第一个节点
 findAndUpdateLastNode(lastNode, lastNodeIdx, i, nowIdx);
 parents[nowIdx] = lastNodeIdx;
 } else {
 int preNodeIdx = nodeIdx[i][j - 1];
 Log(&#34;\t\t\tpreNodeIdx:%d\n&#34;, preNodeIdx);

 int distance = dis[child[nowIdx]][child[preNodeIdx]] -
 delta[nowIdx] - delta[preNodeIdx];
 Log(&#34;\t\t\tdistance:%d dis:%d(%d %d) del:%d %d\n&#34;, distance,
 dis[child[nowIdx]][child[preNodeIdx]], child[nowIdx],
 child[preNodeIdx], delta[nowIdx], delta[preNodeIdx]);
 if (distance == 2) {
 parents[nowIdx] = lastNodeIdx;
 } else {
 findAndUpdateLastNode(lastNode, lastNodeIdx,
 i, nowIdx);
 parents[nowIdx] = lastNodeIdx;
 }
 }
 Log(&#34;\t\t\tlastNode:%d LastNodeIdx:%d\n&#34;, lastNode, lastNodeIdx);
 }
 }
 for (int i = 1; i &lt;= N; ++i) {
 printf(&#34;%d &#34;, parents[i]);
 }
 printf(&#34;\n&#34;);
 return 0;
}
</pre>

hihocoder 1490.Tree Restoration