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 ）
原文：http://www.cnblogs.com/wenruo/p/5891546.html