3745: 斯坦纳树(第三轮03)
题目描述
斯坦纳树是这么一类问题：给定一张图G =< V, E >，和点集V1，你需要找到原图 的一张子图（即原图中删去一些点和边之后得到的图），令子图为G′ =< V′, E′ >， 满足V1 ⊆ V′ ,子图G′连通，且子图中的边权和尽量小。
今天， 牛牛接到了这么一个问题： 给定一棵树G （注意到树也是一种特殊的图， 对应上文的图G），每次给出一个点集V1，求这个点集在树G上的斯坦纳树大小（即 边权和）。
他不会做这个问题，所以提出了一个乱搞的做法：建立一个新的完全图G′，图中 每个点都对应着询问点集V1 中的一个点，两个点之间的边权为其在V1 对应的点的 树上距离。最后将这个完全图的最小生成树大小作为答案。
显然这个做法不是正确的，但是牛牛想知道，这个做法在什么情况下是正确的呢？ 于是他给出了一个1到n 的排列p ,希望你对每个i(1 ≤ i ≤ n),验证这个算法在点集 Vi = {p1 , p2 . . . pi }上的正确性。
输入
第一行一个正整数n，表示树的大小。
接下来n − 1行，每行三个数字u, v, w，表示树上的一条边(u, v),边权为w 。 接下来一行n个正整数，表示排列p。
保证给出的树和排列是合法的。
输出
一行一个长度为n 的0101串，若第i个为0，则表示算法在点集V = {P1, P2, . . . Pi } 上是错误的。否则则表示算法在该点集上是正确的。
样例输入 复制
5
1 2 3
1 5 0
2 3 2
2 4 3
1 3 4 2 5样例输出 复制
11011提示
【样例 1 输入】
5
1 2 3
1 5 0
2 3 2
2 4 3
1 3 4 2 5
【样例 1 输出】
11011
【样例 2 输入】
10
5 9 0
6 9 6
7 6 9
1 7 5
10 1 2
8 10 0
4 10 5
3 4 9
2 5 4
4 5 3 7 8 9 6 2 1 10
【样例 2 输出】
1111111111
【数据范围】
对于20%的数据,2 ≤ n ≤ 10
对于30%的数据,2 ≤ n ≤ 100
对于另外5%的数据，原树是一条链
对于另外25%的数据， 1 ≤ E ≤ 10^9 ,其中E代表每条边的边权 对于100%的数据,2 ≤ n ≤ 3 × 10^5, 0 ≤ E ≤ 10^9