题目链接：http://codeforces.com/problemset/problem/697/D
给你一个有规则的二叉树，大概有1e18个点。
有两种操作：1操作是将u到v上的路径加上w，2操作是求u到v上的路径和。
我们可以看出任意一个点到1节点的边个数不会超过64（差不多就是log2(1e18)），所以可以找最近相同祖节点的方式写。
用一条边的一个唯一的端点作为边的编号（比如1到2，那2就为这条边的编号），由于数很大，所以用map来存。
进行1操作的时候就是暴力加w至u到LCA(u,v)上的各个边，同样加w至v到LCA(u , v)上的各个边。同理，进行2操作的时候也是暴力求和。
下面这是简单的写法
#include <bits/stdc++.h>
using namespace std;
typedef __int64 LL;
map <LL , LL> cnt; int main()
{
int n;
LL choose , u , v , val;
scanf("%d" , &n);
while(n--) {
scanf("%lld" , &choose);
if(choose == ) {
scanf("%lld %lld %lld" , &u , &v , &val);
while(u != v) {
if(u > v) {
cnt[u] += val;
u /= ;
}
else {
cnt[v] += val;
v /= ;
}
}
}
else {
scanf("%lld %lld" , &u , &v);
LL res = ;
while(u != v) {
if(u > v) {
res += cnt[u];
u /= ;
}
else {
res += cnt[v];
v /= ;
}
}
printf("%lld\n" , res);
}
}
return ;
}
下面是我一开始的写法，也A了，不过有点麻烦，可以不看。
#include <bits/stdc++.h>
using namespace std;
typedef __int64 LL;
const int N = 1e3 + ;
vector <int> vc;
vector <LL> q1[N] , q2[N] , ans1 , ans2;
LL x[N] , y[N] , val[N];
int main()
{
int n;
LL choose , u , v;
scanf("%d" , &n);
for(int i = ; i <= n ; ++i) {
scanf("%lld" , &choose);
if(choose == ) {
scanf("%lld %lld %lld" , x + i , y + i , val + i);
vc.push_back(i);
LL num1 = x[i] , num2 = y[i];
q1[i].push_back(num1) , q2[i].push_back(num2);
while(num1 != num2) {
if(num1 > num2) {
num1 /= ;
q1[i].push_back(num1);
}
else {
num2 /= ;
q2[i].push_back(num2);
}
}
}
else {
scanf("%lld %lld" , &u , &v);
LL temp1 = u , temp2 = v , res = ;
ans1.clear() , ans2.clear();
ans1.push_back(temp1) , ans2.push_back(temp2);
while(temp1 != temp2) {
if(temp1 > temp2) {
temp1 /= ;
ans1.push_back(temp1);
}
else {
temp2 /= ;
ans2.push_back(temp2);
}
}
for(int j = ; j < vc.size() ; ++j) {
int l = , r = ans1.size() - , k = ;
while(l + <= r) {
for( ; k + < q1[vc[j]].size() ; ++k) {
if(ans1[l] > q1[vc[j]][k])
break;
if(ans1[l + ] == q1[vc[j]][k + ] && ans1[l] == q1[vc[j]][k]) {
res += val[vc[j]];
}
}
l++;
}
k = , l = , r = ans1.size() - ;
while(l + <= r) {
for( ; k + < q2[vc[j]].size() ; ++k) {
if(ans1[l] > q2[vc[j]][k])
break;
if(ans1[l + ] == q2[vc[j]][k + ] && ans1[l] == q2[vc[j]][k]) {
res += val[vc[j]];
}
}
l++;
} l = , r = ans2.size() - , k = ;
while(l + <= r) {
for( ; k + < q1[vc[j]].size() ; ++k) {
if(ans2[l] > q1[vc[j]][k])
break;
if(ans2[l + ] == q1[vc[j]][k + ] && ans2[l] == q1[vc[j]][k]) {
res += val[vc[j]];
}
}
l++;
}
k = , l = , r = ans2.size() - ;
while(l + <= r) {
for( ; k + < q2[vc[j]].size() ; ++k) {
if(ans2[l] > q2[vc[j]][k])
break;
if(ans2[l + ] == q2[vc[j]][k + ] && ans2[l] == q2[vc[j]][k]) {
res += val[vc[j]];
}
}
l++;
}
}
printf("%lld\n" , res);
}
}
return ;
}