# Codeforces 1087A - Right-Left Cipher

## 题解链接

https://lucien.ink

## 题目链接

http://codeforces.com/contest/1087/problem/A

## 实现

https://pasteme.cn/2801

#include <bits/stdc++.h>
char str[int(1e5) + 7];
int main() {
std::cin >> str;
std::string ans = "";
int len = int(strlen(str)), l = 0, r = len - 1;
bool flag = !bool(len & 1);
while (l <= r) {
if (flag) ans = str[r--] + ans;
else ans = str[l++] + ans;
flag = !flag;
}
std::cout << ans << std::endl;
return 0;
}

# Codeforces 1087B - Div Times Mod

## 题解链接

https://lucien.ink

## 题目链接

http://codeforces.com/contest/1087/problem/B

## 实现

https://pasteme.cn/2802

#include <bits/stdc++.h>
typedef long long ll;
int main() {
ll n, k, ans = 0x3f3f3f3f3f3f3f3f;
std::cin >> n >> k;
for (ll b = k - 1; b >= 1; b--) {
if (n % b == 0) {
ll a = n / b;
ans = std::min(ans, a * k + b);
}
}
std::printf("%lld\n", ans);
return 0;
}


# Codeforces 1087C - Connect Three

## 题解链接

https://lucien.ink

## 题目链接

http://codeforces.com/contest/1087/problem/C

## 实现

https://pasteme.cn/2803

#include <bits/stdc++.h>
struct Node {
int x, y, index;
} node[7];
std::pair<int ,int> ans[int(1e6) + 7];
int cnt = 0;
int main() {
for (int i = 1; i <= 3; i++) std::cin >> node[i].x >> node[i].y, node[i].index = i;
std::sort(node + 1, node + 1 + 3, [](Node a, Node b) { return a.x < b.x; });
int up = node[3].x, down = node[1].x, mid = node[2].x;
std::sort(node + 1, node + 1 + 3, [](Node a, Node b) { return a.y < b.y; });
for (int i = node[1].y; i <= node[3].y; i++) ans[++cnt] = std::make_pair(mid, i);
for (int i = 1; i <= 3; i++) {
if (node[i].x != mid) {
for (int j = std::min(mid, node[i].x), upper = std::max(mid, node[i].x); j <= upper; j++)
ans[++cnt] = std::make_pair(j, node[i].y);
}
}
std::sort(ans + 1, ans + cnt + 1);
cnt = int(std::unique(ans + 1, ans + 1 + cnt) - ans - 1);
std::printf("%d\n", cnt);
for (int i = 1; i <= cnt; i++) std::printf("%d %d\n", ans[i].first, ans[i].second);
return 0;
}

# Codeforces 1087D - Minimum Diameter Tree

## 题解链接

https://lucien.ink

## 题目链接

http://codeforces.com/contest/1087/problem/D

## 实现

https://pasteme.cn/2804

#include <bits/stdc++.h>
const int maxn = int(2e5) + 7, maxm = int(4e5) + 7;
struct Lca {
struct { int next, to, val; } edge[maxm]{};
void addedge(int u, int v) {
}
explicit Lca() {
cnt = 0;
memset(up, 0xff, sizeof(up));
}
void init(int n) {
std::queue<int> que;
que.emplace(dep[1] = 1);
int u, v;
while (!que.empty()) {
u = que.front(), que.pop();
for (int i = head[u]; ~i; i = edge[i].next) {
v = edge[i].to;
if (dep[v]) continue ;
up[v][0] = u, dep[v] = dep[u] + 1, que.push(v);
}
}
for (int j = 1; j <= 20; j++)
for (int i = 1; i <= n; i++)
if (~up[i][j - 1])
up[i][j] = up[up[i][j - 1]][j - 1];
}
int query(int u, int v) {
if (dep[u] < dep[v]) std::swap(u, v);
int tmp = dep[u] - dep[v];
for (int j = 0; tmp; j++)
if (tmp & (1 << j)) tmp ^= (1 << j), u = up[u][j];
if (u == v) return v;
for (int j = 20; j >= 0; j--) {
if (up[u][j] != up[v][j]) {
u = up[u][j], v = up[v][j];
}
}
return up[u][0];
}
} lca;
int deg[maxn], n, s, leaf[maxn], cnt;
int main() {
std::scanf("%d%d", &n, &s);
if (n == 2) return 0 * std::printf("%d\n", s);
for (int i = 1, u, v; i < n; i++) {
std::scanf("%d%d", &u, &v);
deg[u]++, deg[v]++;
}
lca.init(n);
for (int i = 1; i <= n; i++) if (deg[i] == 1) leaf[++cnt] = i;
int pre = leaf[1], min = 0x3f3f3f3f, min_dep = lca.dep[leaf[1]];
for (int i = 2; i <= cnt; i++) {
pre = lca.query(pre, leaf[i]);
min = std::min(min_dep + lca.dep[leaf[i]] - lca.dep[pre] * 2, min);
min_dep = std::min(min_dep, lca.dep[leaf[i]]);
}
min >>= 1;
printf("%.15lf\n", double(s) / double(min * cnt) * min * 2);
return 0;
}