[Codeforces] 894D. Ralph And His Tour in Binary Country
題目連結: http://codeforces.com/problemset/problem/894/D 看了題解又問了人才會這題QAQ 本題作法我覺得好暴力(?，首先要觀察出這題第$i$條邊固定連接$ \lfloor \frac{i+1}{2} \rfloor $跟$i+1$的話，那給定的這棵樹就一定會是一棵完滿二元樹，深度必定為$\log_2(n)$，接著我們要預處理這棵樹，把每個點到其子樹們（包含自己）的距離算出來並排序好（這裡可以用merge sort的merge方法把兩棵子樹merge好），那我們要查詢的時候就只要往上走，並把我另外一邊的子樹可以走到的節點們通通加起來就好了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back #define SZ(x) ((int)(x).size()) #define ALL(x) begin(x), end(x) typedef pair<lld,int> PLI; #define FF first #define SS second const int N = 1000000 + 5; vector<lld> dis[N], sum[N]; lld len[N]; void build(int,int); lld go(int,lld,int); PLI get_val(int,lld); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, q; cin>>n>>q; for(int i=2;i<=n;i++) cin>>len[i]; build(1, n); while(q--){ int w, l; cin>>w>>l; cout<<go(w, l, n)<<'\n'; } return 0; } void build(int id, int mx){ if(id > mx) return; const int lc = id*