首页 > 代码库 > CodeForces 696A（Lorenzo Von Matterhorn ） & CodeForces 696B（Puzzles ）
CodeForces 696A（Lorenzo Von Matterhorn ） & CodeForces 696B（Puzzles ）
A，给一棵完全二叉树，第一个操作，给两个点，两点路径上的所有边权值都增加w，第二个操作，给两个点，求两点路径上的所有边权值和。
我看一眼题就觉得是树链剖分，而我又不会树链剖分，扔掉。
后来查了题解，首先数据范围是1e18不可能是树剖，其次完全二叉树啊！不是普通的树啊！！sb。。。
//我做过此题，没做出来，被学弟教会。。虽然我做的题少，但我一向觉得至少自己做过的题都是记得的。。。但是。。。。
#include <algorithm>#include <iostream>#include <map>using namespace std;typedef long long ll;map<ll, ll> mp;int main(){ ll q, op, u, v, w, ans; for (cin >> q; q--; ) { cin >> op >> u >> v; if (op == 1) { cin >> w; while (u != v) { if (u < v) swap(u, v); mp[u] = mp[u] + w; u /= 2; } } else { ans = 0; while (u != v) { if (u < v) swap(u, v); ans += mp[u]; u /= 2; } cout << ans << endl; } } return 0;}
B。树形dp，每一个兄弟结点在该节点的前面的概率肯定是0.5啊。我还想了好久。然后就水。
#include <vector>#include <cstdio>std::vector<int> tr[100005];int sz[100005], n, tmp;double ans[100005];int dfs(int u) { for (int v: tr[u]) sz[u] += dfs(v); return ++sz[u]; }void dfs(int u, double d) { ans[u] = d+1; for (int v: tr[u]) dfs(v, (sz[u]-1-sz[v])/2.0+ans[u]); }int main(){ scanf("%d", &n); for (int i = 2; i <= n; ++i) scanf("%d", &tmp), tr[tmp].push_back(i); dfs(1); dfs(1, 0); for (int i = 1; i <= n; ++i) printf("%f%c", ans[i], i==n?‘\n‘:‘ ‘); return 0;}
CodeForces 696A（Lorenzo Von Matterhorn ） & CodeForces 696B（Puzzles ）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。