题目大意：

给你一颗n个节点的完全二叉树，从根节点标号为1。标号为x的节点的左、右儿子标号分别为：2x、2x+1。这棵树的每个节点的权值为它本身的标号。现在告诉你有m次操作，每次操作要么就是把一个点变成给定值，要么就是让你输出经过给定某点的一条最长路径的长度。（一条路径的长度就是它经过的每个点的权值和，包括端点）
数据范围：$n<1e8，m<1e5$

分析：

首先，显然对于这种树上的问题，直觉上就是要划分子树或者一层一层的遍历才是比较快的。

dp的建立：

设：dp[ i ]表示标号为i的节点向下最长能走多长的路径。
那么对于每一次的查询，就是从这个节点开始，一直向上遍历，枚举它的每个祖先作为根节点的时候得到的最长路径，时间：O( log n ) 。每一次更新就是更新该节点，并向上遍历更新他的每个祖先，时间：O( log n )。

关于hash优化：

但是发现，如果要储存每个 dp 的值，那就需要 1e8 的空间，这显然是存不开的。但是想到，在更改之前，对于每个点的查询，我是可以以O( log n )的时间求出他的对应的 dp 值的，详细求法在下文说。然后假如我只记录我需要修改的点，那么最多只需要记录 m*log n 个点就足够了，这个是可以用 hash 表来记录的。

下面来说明对于一次查询操作，得到一个点 dp[ i ] 的具体操作过程：

如果该点并没有被存到hash表中就说明以这个点为根节点的子树的所有节点都没有被更改过，那么我就只要比较它的左右儿子的子节点层数，如果层数相等，我就加上它的右子节点，如果层数不等，就加上它的左子节点。之后继续向下判断。如果该点被hash记录过了，那么就是这个值，直接返回就好。

代码：

#include<bits/stdc++.h>
using namespace std;

int n;int q;
char s[20];
map<int,long long int>f;
map<int,long long int>a;

int deep(int x)
{
    int ans=0;
    while(x<=n)
    {
        ans++;
        x*=2;
    }
    return ans;
}
long long int get_v(int x)//得到以x号结点开始向下能走到的最大值
{
    if(x>n)return 0;
    if(f.count(x)>0)return f[x];
    long long int ans=(a.count(x)?a[x]:x);
    if(deep(x)==1)return ans;
    if(deep(x*2+1)==deep(x*2))
    {
        ans+=get_v(x*2+1);
    }
    else
    {
        ans+=get_v(x*2);
    }
    return ans;
}
void change()
{
    int x;long long int v;
    scanf("%d%lld",&x,&v);//标号x结点值变为v
    a[x]=v;
    long long int t=max(get_v(x*2+1),get_v(x*2))+v;
    f[x]=t;
    while(x>1)
    {
        x/=2;
        f[x]=max(get_v(x*2),get_v(x*2+1))+(a.count(x)?a[x]:x);
    }
}
void query()
{
    int x;
    scanf("%d",&x);
    if(x==1)
    {
        printf("%lld\n",get_v(x*2)+get_v(x*2+1)+(a.count(x)?a[x]:x));
        return ;
    }
    long long int k=get_v(x);
    long long int best=get_v(x*2)+get_v(x*2+1)+(a.count(x)?a[x]:x);
    while(x>1)
    {
        int other;
        if(x%2==0)other=x+1;
        else other=x-1;
        x/=2;
        k+=(a.count(x)?a[x]:x);
        long long int temp=k+get_v(other);
        if(temp>best)best=temp;
    }
    printf("%lld\n",best);
}


int main()
{
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        a.clear();f.clear();
        while(q--)
        {
            scanf("%s",s);
            if(s[0]=='q')query();
            if(s[0]=='c')change();
        }
    }
    return 0;
}

另附测试数据生成代码（输入n m即可随机输出若干组测试数据）：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,m;
    srand( (unsigned)time( NULL ) );
    //freopen()
    scanf("%d%d",&n,&m);
    while(m--)
    {
        if(rand()%2==1)
        {
            printf("query %d\n",(rand()%n)+1);
        }
        else
        {
            printf("change %d %d\n",(rand()%n)+1,(rand()%n)+1);
        }
    }
}