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 == ) {
cin >> w;
while (u != v) {
if (u < v) swap(u, v);
mp[u] = mp[u] + w;
u /= ;
}
} else {
ans = ;
while (u != v) {
if (u < v) swap(u, v);
ans += mp[u];
u /= ;
}
cout << ans << endl;
}
}
return ;
}
B。树形dp，每一个兄弟结点在该节点的前面的概率肯定是0.5啊。我还想了好久。然后就水。
#include <vector>
#include <cstdio>
std::vector<int> tr[];
int sz[], n, tmp;
double ans[];
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+; for (int v: tr[u]) dfs(v, (sz[u]--sz[v])/2.0+ans[u]); }
int main()
{
scanf("%d", &n);
for (int i = ; i <= n; ++i) scanf("%d", &tmp), tr[tmp].push_back(i);
dfs(); dfs(, );
for (int i = ; i <= n; ++i) printf("%f%c", ans[i], i==n?'\n':' ');
return ;
}