高速道路の建設 / Construction of Highway
这个操作长得很像 LCT 中的 access。
于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。
因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ 的，所以时间复杂度 $\mathcal{O}(n\log^2 n)$。
柵 / Fences
不会
テント / Tents
我们先不管不能为空的限制，最后减去 $1$ 即可。
设 $dp_{i,j}$ 为 $i$ 行 $j$ 列时的答案。转移时放若干个帐篷并强制在最后一行放一个：
- 不放帐篷：$dp_{i-1,j}\to dp_{i,j}$；
- 加一个帐篷，需要占用一行一列，方向任意：$4\times dp_{i-1,j-1}\times j\to dp_{i,j}$；
- 加两个帐篷，需要占用一行两列：$dp_{i-1,j-2}\times {j\choose 2}\to dp_{i,j}$；
- 加两个帐篷，需要占用两行一列：$dp_{i-2,j-1}\times j\times (i-1)\to dp_{i,j}$。
修行 / Asceticism
我们相当于要求 $\sum_{i=1}^{n-1}[p_i>p_{i+1}]=k-1$ 的排列数。
有一个奇妙的结论是，当 $p_i$ 是 $[0,1)$ 中的实数时方案数和排列数是相等的。证明不会。
考虑构造 $a_i=[p_{i-1}>p_i]+p_i-p_{i-1}$。可以发现 $a_i\in[0,1)$，而且一组 $a_i$ 唯一对应一组 $p_i$。
那么我们相当于要求 $k-1\leq\sum a_i<k$ 的概率。容斥一下，变成求 $\sum a_i<k$ 的概率。
我们知道（其实我并不知道），$n$ 个 $[0,+\infty)$ 的随机实数的和 $<k$ 的概率为 $\frac{k^n}{n!}$。
然而现在有一个上界的限制，所以我们只要再容斥一下就好了。
道路網の整備 / Road Service
猜想新加的 $k$ 条边都连到一个点上时是很优秀的。
那么直接瞎随机就好了，每个点跑几秒都可以拿到 $14$ 分，跑五个小时应该就能拿 $18$ 分了。反正我每个点只要跑一个小时就可以到 17.5 分以上（
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=1000+10;
const double eps=1e-7;
mt19937 rnd(time(0));
int n,k,W0,s;
vector<int> E[N],G[N];
struct edge { int u,v; } e[N];
int dis[N];
int bfs(int s) {
memset(dis,0,sizeof(dis)); dis[s]=1;
queue<int> Q; Q.push(s);
while (!Q.empty()) {
int u=Q.front(); Q.pop();
for (int v:E[u])
if (!dis[v]) dis[v]=dis[u]+1,Q.push(v);
}
int res=0;
for (int i=1;i<=n;++i) res+=dis[i]-1;
return res;
}
ll calc() {
for (int i=1;i<=n;++i) G[i]=E[i];
for (int i=1;i<=k;++i) {
E[e[i].u].emplace_back(e[i].v);
E[e[i].v].emplace_back(e[i].u);
}
ll res=0;
for (int i=1;i<=n;++i) res+=bfs(i);
for (int i=1;i<=n;++i) E[i]=G[i];
return res/2;
}
void print(ll ans) {
double score=18*pow(20,1-1.0*ans/W0);
printf("%.10lf\n",score);
if (score>17.5) {
FILE *fp=fopen("road.out","w");
for (int i=1;i<=k;++i) fprintf(fp,"%d %d\n",e[i].u,e[i].v);
fclose(fp); exit(0);
}
}
int main() {
freopen("road.in","r",stdin);
n=read(),k=read(),W0=read();
for (int i=1;i<n;++i) {
int u=read(),v=read();
E[u].emplace_back(v),E[v].emplace_back(u);
}
ll ans=1e18;
s=rnd()%n+1;
for (int i=1;i<=k;++i) e[i]=(edge){s,rnd()%n+1};
ll now=calc();
if (now<ans) ans=now,print(ans);
while (1) {
int p=rnd()%k+1,ov=e[p].v; e[p].v=rnd()%n+1;
now=calc();
if (now<ans) ans=now,print(ans);
else e[p].v=ov;
}
return 0;
}最悪の記者 3 / Worst Reporter 3
显然每个人的运动是有周期的，而这个周期可以直接算出来。还可以发现，每一个人的周期都是前一个人周期的倍数。
那么可能的周期只有 $\log$ 种，每次直接暴力对每种周期对应的区间求个交即可。
航空路線図 / Airline Route Map
咕咕咕
ビ太郎のパーティー / Bitaro’s Party
注意到 $\sum y_i\leq 10^5$，因此可以考虑根号分治。
如果 $y_i\geq \sqrt{n}$，这样的询问只会有至多 $\mathcal{O}(\sqrt{n})$ 个，可以直接拓扑排序求最长路。
如果 $y_i<\sqrt{n}$，我们可以对每个点预处理出距离它最远的 $\sqrt{n}$ 个点，这样子直接查询即可。这个预处理相当于把所有入边对应的最远点合并，归并后每个点只保留最大的 $dis$ 即可。
防犯ゲート / Security Gate
不会
飴 / Candies
和 CTSC2007 数据备份 是一个套路。
考虑贪心，我们每次选一个能选的最大的然后把旁边两个删掉即可，用堆维护。
然而这样子显然是有问题的，因为我们之后可能会放弃选这个而选旁边的两个。于是我们在选 $p$ 时把 $a_{l_p}+a_{r_p}-a_p$ 加入堆中即可（相当于维护反悔）。这个 $l_p$ 和 $r_p$ 可以用双向链表维护。
図書館 / Library
我们可以先用 $\mathcal{O}(n)$ 次询问找到一个端点。
接着我们找到与这个端点相邻的数。考虑二分，假设 $[L,mid]$ 的答案和 $[L,mid]\cup{i}$ 的答案相同，说明相邻的数在 $[L,mid]$ 中，否则在 $[mid+1,R]$ 中。
重复这个过程就可以确定整个序列了。询问数是 $\mathcal{O}(n\log n)$ 的。
イノシシ / Wild Boar
不会