【hdu 6161】Big binary tree（二叉树、dp）

题意

有一个完全二叉树。编号i的点值是i，操作1是修改一个点的值为x，操作2是查询经过点u的所有路径的路径和最大值。10^5个点，108次操作。

题解

用map储存修改过的点的值val，和dp[i]，表示i子树的最大路径和。

查询就是考虑两种情况，经过u点的两个孩子和经过它的一个孩子再经过它父亲，需要边走到根节点边更新答案。

代码

#include <cstdio>

#include <algorithm>

#include <map>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))

typedef long long ll;

const ll mod=1000000007;

const int N=201000;

map<int,ll>dp,val;

int n,m;

char o[10];

ll get(int u){

	return val.count(u)?val[u]:u;

}

ll cal(int u){

	if(!u||u>n)return 0;

	if(dp.count(u))return dp[u];

	int v,ls=0,rs=0;

	for(v=u;v<=n;++ls,v<<=1);

	for(v=u;v<=n;++rs,v=v<<1|1);

	if(ls!=rs) v=n;

	else v>>=1;

	ll ans=0;

	for(;v>=u;ans+=v,v>>=1);

	return ans;

}

void update(int u,ll x){

	val[u]=x;

	while(u){

		dp[u]=max(cal(u<<1),cal(u<<1|1))+get(u);

		u>>=1;

	}

}

ll query(int u){

	ll ans=get(u)+cal(u<<1)+cal(u<<1|1);

	ll tot=cal(u);

	while(u){

		ans=max(ans,tot+cal(u^1)+get(u>>1));

		u>>=1;tot+=get(u);

	}

	return ans;

}

int main() {

	while(~scanf("%d%d",&n,&m)){

		dp.clear();val.clear();//又忘记了。。

		while(m--){

			int u;ll x;

			scanf("%s%d",o,&u);

			if(o[0]=='q'){

				printf("%lld\n",query(u));

			}else{

				scanf("%lld",&x);

				update(u,x);

			}

		}

	}

	return 0;

}

巴特西

【hdu 6161】Big binary tree（二叉树、dp）

题意

题解

代码

最新文章

热门文章