题目链接：http://codeforces.com/contest/697/PRoblem/C
【中文题意】给你一棵完全二叉树，第一层为 1，第二层从左到右为2，3。依次往下…….一共有n个操作，有两种操作。 第一种操作：1 u,v,w。将u到v之间的路径上的每一条边的值+w。 第二种操作：2 u,v。输出从u到v之间的路径上的边的权值和。 【思路分析】首先对于完全二叉树来说，1e18这个数据范围太大，如果构建一棵这样的二叉树，不仅时间上会超过限制，而且空间上也会超过限制。所以呢，我们没有必要把所有的结点都表示出来，只需用到哪个表示哪个即可。那么怎么更新路径和查找路径呢，更新路径的话类似我们查找两个结点的最近公共祖先，把结点的值存入map里面即可，另外一条边的权值可以加在一个点上面，因为要查找边肯定从点开始。 【AC代码】
#include<cstdio>#include<iostream>#include<cstring>#include<cmath>#include<queue>#include<stack>#include<map>#include<algorithm>using namespace std;#define LL long longmap<LL,LL >ma;int main(){ int n; while(~scanf("%d",&n)) { ma.clear(); int choice; for(int i=1;i<=n;i++) { scanf("%d",&choice); LL u,v,w; if(choice==1) { scanf("%lld %lld %lld",&u,&v,&w); while(u!=v) { if(u>v) { ma[u]+=w; u/=2; } else { ma[v]+=w; v/=2; } } } else { scanf("%lld%lld",&u,&v); LL re=0; while(u!=v) { if(u>v) { re+=ma[u]; u/=2; } else { re+=ma[v]; v/=2; } } printf("%lld/n",re); } } } return 0;}新闻热点
疑难解答
