传送门： CodeForces - 697C

原创--原创--原创

第一次自己A了一道感觉有点难度的题；

题意：在一个类似于二叉树的图上，1 : u ，v，w 表示从u到v的所以路都加上w的费用；

　　　　　　　　　　　　　　　　2 : u，v  输出u，v间的花费；

思路：自己看这个图，一直想写线段树，后来想想LCA求最近公共祖先，一步一步向上跳的思想还可以，

　　　就用 每个点 表示这个点到父节点所需要的花费；计算的时候，和求LCA相似，累加到最近公共祖先的花费；

　　　还有就是用map< ll ,  ll >存每个节点的信息；

#include
#include
#include
#include
#include
#include
#include

        while(u!=v)  
        {  
            mp\[u\]+=w;  
            mp\[v\]+=w;  
            u=u/;  
            v=v/;  
        }  
    }  
    else  
    {  
        scanf("%lld%lld",&u,&v);  
        ll ans = ;  
        if(log2(u)<log2(v))swap(u,v);  
        while(log2(u)>log2(v))  
        {  
            ans+=mp\[u\];  
            u/=;  
        }  
        while(u!=v)  
        {  
            ans+=mp\[u\];  
            ans+=mp\[v\];  
            u=u/;  
            v=v/;  
        }  
     //   if(u!=1)ans+=mp\[u\];  
        printf("%lld\\n",ans);  
       // if(ans==94)cout<<"\*"<<mp\[6\]<<endl;  
    }  
}

return ;  

}