HDU 4836 The Query on the Tree lca || 欧拉序列 || 动态树

HDU 4836 The Query on the Tree lca || 欧拉序列 || 动态树

大家好,又见面了,我是全栈君。

lca的做法还是非常明显的。简单粗暴,

只是不是正解。假设树是长链就会跪,直接变成O(n)、、

最后跑的也挺快,出题人还是挺阳光的。。

动态树的解法也是听别人说能ac的。预计就是放在splay上剖分一下,做法还是比較复杂的。,,

来一发lca:

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=20010;
int head[maxn],tol,dp[maxn],fa[maxn][20],dep[maxn],weight[maxn];
struct Edge{
    int next,to;
    Edge(int _next=0,int _to=0){
        next=_next;to=_to;
    }
}edge[10*maxn];
void addedge(int u,int v){
    edge[tol]=Edge(head[u],v);
    head[u]=tol++;
}
void bfs(int s){
    queue<int> q;
    dep[s]=0,fa[s][0]=s;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;
            if(v==fa[u][0])continue;
            fa[v][0]=u;
            dep[v]=dep[u]+1;
            q.push(v);
        }
    }
}
int LCA(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=19;i>=0;i--)if((1<<i)&(dep[x]-dep[y]))x=fa[x][i];
    if(x==y)return x;
    for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void dfs(int u,int pre){
    dp[u]=weight[u];
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(v==pre)continue;
        dfs(v,u);
        dp[u]+=dp[v];
    }
}
int move(int x,int d){
    for(int i=19;i>=0;i--)
        if(d&(1<<i))x=fa[x][i];
    return x;
}
int main()
{
     int T;
     cin>>T;
     for(int t=1;t<=T;t++){
         int n;
         scanf("%d",&n);
         memset(head,-1,sizeof(head));tol=0;
         for(int i=1;i<n;i++){
             int x,y;
             scanf("%d%d",&x,&y);
             addedge(x,y);
             addedge(y,x);
         }
         bfs(1);
         for(int i=1;i<=n;i++)scanf("%d",&weight[i]);
         dfs(1,-1);
         printf("Case #%d:\n",t);
         int Q;
         scanf("%d",&Q);
         int root=1;
         while(Q--){
             char op[10];
             int x,y;
             scanf("%s",op);
             if(op[0]=='R'){
                 scanf("%d",&x);
                 root=x;
             }
             else if(op[0]=='C'){
                 scanf("%d%d",&x,&y);
                 int dd=x;
                 while(1){
                     dp[dd]+=y-weight[x];
                     if(dd==1)break;
                     dd=fa[dd][0];
                 }
weight[x] = y;
             }
             else {
                 scanf("%d",&x);
                 if(x==root)printf("%d\n",dp[1]);
                 else {
                     int lca=LCA(x,root);
                     if(lca==x){
                         int p=move(root,dep[root]-dep[x]-1);
                         //cout<<"han "<<x<<" "<<root<<" "<<dep[root]-dep[x]-1<<endl;cout<<"p="<<p<<endl;
                         printf("%d\n",dp[1]-dp[p]);
                     }
                     else printf("%d\n",dp[x]);
                 }
             }
         }
     }
     return 0;
}

正解应该是树状数组维护欧拉序列,,

bit的神牛教的。,

详见:点击打开链接

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116158.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号