佛山怎么做网站,游戏推广代理平台,网络促销分类 网站促销,商河做网站公司Farmer John 的奶牛们决定为 Farmer Nhoj 农场的奶牛们举办一场编程竞赛。为了使问题尽可能有趣#xff0c;他们花费了大量时间来构造具有挑战性的测试用例。特别是对于一个问题#xff0c;「Haybales」#xff0c;奶牛们需要你的帮助来设计具有挑战性的测试用例。这有关解决…Farmer John 的奶牛们决定为 Farmer Nhoj 农场的奶牛们举办一场编程竞赛。为了使问题尽可能有趣他们花费了大量时间来构造具有挑战性的测试用例。特别是对于一个问题「Haybales」奶牛们需要你的帮助来设计具有挑战性的测试用例。这有关解决以下这个有些奇妙的问题
有一个有序整数数组 x 1 ≤ x 2 ≤ ⋯ ≤ x N x_1 \leq x_2 \leq \dotsb \leq x_N x1≤x2≤⋯≤xN 1 ≤ N ≤ 1 0 5 1 \leq N \leq 10^5 1≤N≤105和一个整数 K K K。你不知道这个数组以及 K K K但你知道对于每个索引 i i i 使得 x j i ≤ x i K x_{j_i} \leq x_i K xji≤xiK 的最大索引 j i j_i ji。保证有 i ≤ j i i\le j_i i≤ji 以及 j 1 ≤ j 2 ≤ ⋯ ≤ j N ≤ N j_1\le j_2\le \cdots \le j_N\le N j1≤j2≤⋯≤jN≤N。
给定这些信息Farmer John 的奶牛需要构造任意一个数组以及整数 K K K 与该信息一致。构造需要满足对于所有 i i i 有 0 ≤ x i ≤ 1 0 18 0 \leq x_i \leq 10^{18} 0≤xi≤1018并且 1 ≤ K ≤ 1 0 18 1 \leq K \leq 10^{18} 1≤K≤1018。
可以证明这一定是可行的。请帮助 Farmer John 的奶牛们解决这一问题 先将 j i j_i ji 都加上 1 1 1这样 j i j_i ji 就表示最大的满足 x j i x i K x_{j_i}x_iK xjixiK 的下标。
在 i i i 和 j i j_i ji 之间连边最终会得到一棵树以 n 1 n1 n1 为根。
由于 x j i x_{j_i} xji 与 x i x_{i} xi 的差大约为 K K K于是通过人类智慧猜测 x i x_i xi 形如 x ⋅ K y ( 0 ≤ y K ) x\cdot Ky(0\le yK) x⋅Ky(0≤yK)。 x x x 显然与深度有关下面考虑求 y y y。
根据 x j i x i K x_{j_i}x_iK xjixiK可得 y u y_u yu 大于其所有儿子的 y y y 值意味着 y u ≥ y_u\ge yu≥ 其子树所有的 y y y 值。通过人类智慧发现树的 dfs 序完美不符合条件于是令 y u K − d f n u y_uK-dfn_u yuK−dfnu这样就行了。
注意 x i x_i xi 为自然数 K K K 只需 ≥ n 1 \ge n1 ≥n1 即可。
时间复杂度 O ( n ) O(n) O(n)。
#includebits/stdc.h
using namespace std;
const int N1e510;
int n,k,dep[N],ans[N],num;
int head[N],nxt[N1],to[N1],cnt;
void add(int u,int v)
{to[cnt]v;nxt[cnt]head[u];head[u]cnt;
}
void dfs(int u)
{ans[u]--k;for(int ihead[u];i;inxt[i]) dep[to[i]]dep[u]1,dfs(to[i]);
}
int main()
{cin.tie(0)-sync_with_stdio(0);cinn;cout(knumn2)\n;for(int i1,x;in;i){cinx;add(x1,i);}dfs(n1);for(int i1;in;i) cout1ll*num*(dep[1]-dep[i])ans[i]\n;
}
