こういう回ねー.
The 数学という感じでやられてしまった.
AとBは通した. Cを通せる頭がなかった.
1924 -> 1910(-14).
A. Lorenzo Von Matterhorn
問題概要
頂点 1 を根とする根付き木がある.
任意の頂点 は, 頂点 に双方向に行き来できる道を持つ.
最初, 任意の道の通行料は無料である.
このとき, 個の, 次のイベントを処理せよ.
- : 頂点 を結ぶパス上の道の通行料を 上昇させる.
- : 頂点 を結ぶパス上の道の通行料の和を出力する.
与えられる は, を満たす.
解法
まず, が小さい.
また, の経路長の最大は . この経路は, 貪欲に遡る(深さが深い方がその親へ移動することを繰り返す)ことでそのオーダーで求まる.
関与する頂点は高々 なので, 普通に保存できそう.
具体的には, 関与した頂点を map で管理しておけばよい.
結局 となる.
ソース
#include<bits/stdc++.h> using namespace std; typedef long long int64; int main() { int64 Q; map< pair< int64, int64 >, int64 > data; cin >> Q; while(Q--) { int64 type, v, u, w; cin >> type; if(type == 1) { cin >> v >> u >> w; while(v != u) { if(u > v) { data[{u, u / 2}] += w; u /= 2; } else { data[{v, v / 2}] += w; v /= 2; } } } else { cin >> v >> u; int64 ret = 0; while(v != u) { if(u > v) { ret += data[{u, u / 2}]; u /= 2; } else { ret += data[{v, v / 2}]; v /= 2; } } cout << ret << endl; } } }
B. Puzzles
問題概要
頂点の数が の根付き木がある.
頂点 1 から DFS することを考える.
ある頂点から子に移動するとき, 一様にランダムな順序に移動する.
各頂点について, 何番目に, はじめてその頂点に移動されるか, その期待値を求めよ.
解法
まず前計算として, 任意の頂点 を根とする部分木の頂点数 を求めておく. 言い換えると, は 頂点 に訪問したとき, 親に戻るまでに訪れる頂点の個数である. これはDFSで. .
任意の頂点 から, その子のある頂点 に移動することを考える.
の期待値は, 以外の子 に依存する.
について との関係をみると, それぞれ を訪れる前に訪問するか, 訪れた後に訪問するかのどちらかである. よって, の訪問を終えるまでの期待値は である. これはそれぞれに対して独立であるため, の期待値は の期待値である.
ソース
組み合わせだつらいと一瞬なってしまった.
#include<bits/stdc++.h> using namespace std; int N; vector< int > tree[100000]; int subtree[100000]; double F[100000]; int rec(int idx) { subtree[idx] = 1; for(int to : tree[idx]) subtree[idx] += rec(to); return(subtree[idx]); } void calc(int idx, int par = -1) { for(int to : tree[idx]) { F[to] = (subtree[idx] - subtree[to] - 1) * 0.5; F[to] += F[idx] + 1.0; calc(to); } } int main() { scanf("%d", &N); for(int i = 1; i < N; i++) { int R; scanf("%d", &R); tree[--R].push_back(i); } rec(0); F[0] = 1.0; calc(0); for(int i = 0; i < N; i++) { printf("%.10lf ", F[i]); } }