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