题目描述

给定一个包含 $n$ 个节点的树 $T$，其中每条边都有一个正整数权值。 现在你需要向这个树中添加 $n - 1$ 条边，得到一个新的简单无向图$^\texttt{[1]}$ $G$，使得： $\hspace{23pt}\bullet\,$$T$ 是 $G$ 唯一的最小生成树$^\texttt{[2]}$； $\hspace{23pt}\bullet\,$设 $T$ 的边权之和为 $x$。对于 $T$ 中的任意一条边，如果将 $G$ 中对应的边删除得到 $G^\prime$，那么 $G^\prime$ 是连通图$^\texttt{[3]}$，且 $G^\prime$ 最小生成树的边权之和恰好等于 $x + 1$。 如果不存在合法的添加方法，请输出 $\texttt{No}$。 【名词解释】 简单无向图$^\texttt{[1]}$：指不包含自环（连接节点自身的边）和重边（两个节点之间存在多条边）的无向图。即任意两个不同节点之间至多只有一条边。 最小生成树$^\texttt{[2]}$：对于一张由 $n$ 个节点构成的连通图，选出 $n-1$ 条边将所有节点连通，且使得这 $n-1$ 条边的权重之和最小，这样的结构称为最小生成树。 连通图$^\texttt{[3]}$：如果图中的任意两个顶点之间都存在路径相连，则称这个图是连通图。官方中文

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $t\left(1\leq t\leq 10^4\right)$ 代表数据组数，每组测试数据描述如下：官方中文

第一行输入一个整数 $n\left(4 \leq n \leq 2\times 10^5 \right)$。 此后 $n-1$ 行，第 $i$ 行输入三个整数 $u_i,v_i,w_i\left(1 \leqq u_i, v_i \leqq n;\, u_i \neq v_i;\,1 \leq w_i \leq 10^9 \right)$ 表示树上第 $i$ 条边连接节点 $u_i$ 和 $v_i$，权值为 $w_i$。保证树连通。官方中文

除此之外，保证单个测试文件的 $n$ 之和不超过 $2\times 10^5$。官方中文

输出格式

对于每组测试数据，新起一行。官方中文

如果不存在合法的构造方案，请输出 $\texttt{No}$；否则，请参考下方格式输出。 $\hspace{23pt}\bullet\,$第一行输出 $\texttt{Yes}$。 $\hspace{23pt}\bullet\,$之后的 $n-1$ 行，每行输出三个整数 $u, v, w\left(1\leq u,v\leq n;\,u \ne v;\,1 \leq w \leq 2\times 10^9 \right)$，代表添加一条边权为 $w$ 的边连接 $u, v$。官方中文

您可以以任何大小写形式输出答案。例如，字符串 $\texttt{yEs}$、$\texttt{yes}$ 和 $\texttt{Yes}$ 都将被视为肯定的回答。 如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。官方中文