*2500 的黑(
首先不考虑最小化字典序,我们发现 \(res_i \ge \dfrac{2}{deg_u}\)。意思是理想的状态就是在一段周期内平均分配。
这个下界是可以达到的,根据连向父亲的边的的调整连向儿子的边即可,这个构造是容易的。
于是可以发现 \(res_i\) 的最小值是独立的,只要最小化每个 \(res_i\) 就最小化了字典序。好诈骗啊(((
时间复杂度 \(O(n)\)。为什么 \(n\) 只开到 \(100\)(
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 110;
int n, head[maxn], len, deg[maxn];
ldb a[maxn];
struct edge {
int to, id, next;
} edges[maxn << 1];
void add_edge(int u, int v, int id) {
edges[++len].to = v;
edges[len].id = id;
edges[len].next = head[u];
head[u] = len;
}
void dfs(int u, int fa) {
ldb k = u == 1 ? 0 : fmod(a[u] + 1, 2);
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to, id = edges[i].id;
if (v == fa) {
continue;
}
k = fmod(k + 2. / deg[u], 2);
a[v] = k;
printf("1 %d ", id);
if (k < 1) {
printf("%d %d %.12Lf\n", u, v, k);
} else {
printf("%d %d %.12Lf\n", v, u, k - 1);
}
dfs(v, u);
}
}
void solve() {
scanf("%d", &n);
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
add_edge(u, v, i);
add_edge(v, u, i);
++deg[u];
++deg[v];
}
printf("%d\n", n - 1);
dfs(1, -1);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}