Least Common Ancestors
节点范围是1~1e18，至多1000次询问。
只要不断让深的节点退一层（>>1）就能到达LCA。
用点来存边权，用map储存节点和父亲连边的权值。
代码语言：javascript复制#include<cstdio>
#include<map>
#define ll long long
using namespace std;
map<ll,ll>m;
ll u,v,w;
void add(){
while(u!=v){
if(u<v){
m[v] =w;
v>>=1;
}
else{
m[u] =w;
u>>=1;
}
}
}
ll query(){
ll ans=0;
while(u!=v){
if(u<v){
ans =m[v];
v>>=1;
}else{
ans =m[u];
u>>=1;
}
}
return ans;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i ){
int op;
scanf("%d",&op);
if(op==1){
scanf("%lld%lld%lld",&u,&v,&w);
add();
}else{
scanf("%lld%lld",&u,&v);
printf("%lldn",query());
}
}
}
