題目鏈接：http://codeforces.com/contest/697/PRoblem/C
【中文題意】給你一棵完全二叉樹，第一層為 1，第二層從左到右為2，3。依次往下…….一共有n個操作，有兩種操作。 第一種操作：1 u,v,w。將u到v之間的路徑上的每一條邊的值+w。 第二種操作：2 u,v。輸出從u到v之間的路徑上的邊的權(quán)值和。 【思路分析】首先對于完全二叉樹來說，1e18這個數(shù)據(jù)范圍太大，如果構(gòu)建一棵這樣的二叉樹，不僅時間上會超過限制，而且空間上也會超過限制。所以呢，我們沒有必要把所有的結(jié)點(diǎn)都表示出來，只需用到哪個表示哪個即可。那么怎么更新路徑和查找路徑呢，更新路徑的話類似我們查找兩個結(jié)點(diǎn)的最近公共祖先，把結(jié)點(diǎn)的值存入map里面即可，另外一條邊的權(quán)值可以加在一個點(diǎn)上面，因?yàn)橐檎疫吙隙◤狞c(diǎn)開始。 【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;}新聞熱點(diǎn)
疑難解答
