SPOJ - QTREE (树链剖分)

2024-06-24 06:48
文章标签 树链 剖分 spoj qtree

本文主要是介绍SPOJ - QTREE (树链剖分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

    基础的树链剖分题目,不过是边权,可以向下映射成点权或者按边剖分。

VIEW CODE

#include <iostream>
#include<stdio.h>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<string>
using namespace std;
const int mmax=10010;
const int inf=0x3fffffff;
struct edge
{int st,en,cost;int next;
}E[2*mmax];
int p[mmax],fa[mmax],son[mmax],top[mmax],ID[mmax];
int deep[mmax],cost[mmax],id_[mmax];
bool vis[mmax];
int num;
void add(int st,int en,int cost)
{E[num].st=st;E[num].en=en;E[num].cost=cost;E[num].next=p[st];p[st]=num++;
}
void init()
{memset(p,-1,sizeof p);num=0;
}
struct tree
{int l,r;int max_n;int mid(){return (l+r)>>1;}
}T[4*mmax];
void build(int id,int l,int r)
{T[id].l=l,T[id].r=r;if(l==r){T[id].max_n=cost[ID[l]];return ;}int mid=T[id].mid();build(id<<1,l,mid);build(id<<1|1,mid+1,r);T[id].max_n=max(T[id<<1].max_n,T[id<<1|1].max_n);
}
void updata(int id,int pos,int val)
{if(T[id].l==T[id].r){T[id].max_n=val;return ;}int mid=T[id].mid();if(mid>=pos)updata(id<<1,pos,val);elseupdata(id<<1|1,pos,val);T[id].max_n=max(T[id<<1].max_n,T[id<<1|1].max_n);
}
int query(int id,int l,int r)
{if(l<=T[id].l&&T[id].r<=r)return T[id].max_n;int mid=T[id].mid();int ans=0;if(mid>=l)ans=max(ans,query(id<<1,l,r));if(mid<r)ans=max(ans,query(id<<1|1,l,r));return ans;
}
int dfs(int u)
{vis[u]=1;int cnt=1,tmp=0,e=0,Co=inf;for(int i=p[u];i+1;i=E[i].next){int v=E[i].en;int len=E[i].cost;if(!vis[v]){fa[v]=u;deep[v]=deep[u]+1;cost[v]=len;int tt=dfs(v);cnt+=tt;if(tmp<tt){tmp=tt;e=v;Co=len;}}}son[u]=e;return cnt;
}
int now_cnt;
void new_id(int u)
{ID[now_cnt]=u;id_[u]=now_cnt;now_cnt++;vis[u]=1;if(son[u]){top[son[u]]=top[u];new_id(son[u]);}for(int i=p[u];i+1;i=E[i].next){int v=E[i].en;if(!vis[v])new_id(v);}
}
int solve(int x,int y)
{int ans=0;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]])swap(x,y);ans=max(ans,query(1,id_[top[x]],id_[x]));x=fa[top[x]];}if(x!=y){if(deep[x]>deep[y])swap(x,y);ans=max(ans,query(1,id_[son[x]],id_[y]));}return ans;
}
char str[20];
int main()
{int t,n;scanf("%d",&t);while(t--){init();scanf("%d",&n);for(int i=0;i<n-1;i++){int u,v,cost;scanf("%d %d %d",&u,&v,&cost);add(u,v,cost);add(v,u,cost);}fa[1]=1;deep[1]=0;cost[1]=0;memset(vis,0,sizeof vis);for(int i=1;i<=n;i++)top[i]=i;dfs(1);memset(vis,0,sizeof vis);now_cnt=1;new_id(1);
//        for(int i=1;i<=n;i++)
//            cout<<son[i]<<" ";
//        cout<<endl;
//        system("pause");build(1,1,n);while(1){int a,b;scanf("%s",str);if(!strcmp(str,"DONE"))break;scanf("%d %d",&a,&b);if(!strcmp(str,"QUERY"))printf("%d\n",solve(a,b));if(!strcmp(str,"CHANGE")){int st=E[2*a-2].st;int en=E[2*a-2].en;if(deep[st]>deep[en])swap(st,en);updata(1,id_[en],b);}}//system("pause");}return 0;
}


这篇关于SPOJ - QTREE (树链剖分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1089461

相关文章

树链剖分 + 后缀数组 - E. Misha and LCP on Tree

E. Misha and LCP on Tree  Problem's Link   Mean:  给出一棵树,每个结点上有一个字母。每个询问给出两个路径,问这两个路径的串的最长公共前缀。 analyse: 做法:树链剖分+后缀数组. 记录每条链的串,正反都需要标记,组成一个长串. 然后记录每条链对应的串在大串中的位置,对大串求后缀数组,最后询问就是在一些链

【HDU】5029 Relief grain 树链剖分+离线标记法

传送门:【HDU】5029 Relief grain 题目分析:这题的方法太美妙了! 首先看到这是一颗树,那么很容易想到树链剖分。然后想到可以将查询排个序,然后每一种查询执行完以后更新每个点的最优值。但是这样进行的复杂度太高!尤其是当z给的没有一样的时候尤其如此。 那么我们是否可以找到更加高效的算法? 答案是肯定的! 先简化一下问题,如果这些操作是在线段上进行的,我们怎么求解?

【SPOJ】1825 Free tour II 点分治

传送门:【SPOJ】1825 Free tour II 题目分析:敲了两遍。。。 本题是论文题,具体见漆子超论文《分治算法在树的路径问题中的应用》。 在以root为根的第 i 棵子树上,我们用G[ i ,j ]表示root的第 i 棵子树的路径上严格有 j 个黑点的路径的最长长度。用F[ i ,j ]表示在root为根的第 i 棵子树的路径上不超过 j 个黑点的路径的最长长度。因

【HDU】5221 Occupation【树链剖分】

传送门:【HDU】5221 Occupation 题目分析: 最直接的想法,用一棵树链剖分维护路径,一棵dfs序线段树维护子树。因为每次最多修改一个点,所以修改的时候我们暴力修改每个点就可以了。 my  code: my~~code: #pragma comment(linker, "/STACK:102400000,102400000")#include <stdio.h>#in

【SPOJ】Triple Sums【FFT】

传送门:【SPOJ】Triple Sums 题目分析: 首先我们不考虑 i<j<k i<j<k这个条件,构造多项式: Y=∑xai \qquad\qquad\qquad Y = \sum x^{a_i} 那么 ai+aj+ak=S ai+aj+ak=S的个数即 xai+aj+ak=S x^{a_i+a_j+a_k=S}的个数,等价于 Y3中xS Y^3中x^S的系数。 然后我们考虑容斥

【HDU】5436 Transmigration tree【树链剖分+dp+rmq】

题目链接:【HDU】5436 Transmigration tree #pragma comment(linker, "/STACK:16777216")#include <stdio.h>#include <string.h>#include <vector>#include <algorithm>using namespace std ;typedef long long LL ;

【HDU】5566 Clarke and room【树链剖分+AC自动机】

题目链接:Clarke and room #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define ls ( o << 1 )#define lson ls , l , m#define rs ( o << 1 | 1 )#define rson rs , m + 1 , r#define rt

Open3D mesh 模型精细化处理--中点剖分

目录 一、概述 1.1原理 1.2实现步骤 二、代码实现 2.1关键函数 输入参数 输出参数 三、实现效果 3.1原始mesh 3.2精细化mesh Open3D点云算法汇总及实战案例汇总的目录地址: Open3D点云算法与点云深度学习案例汇总(长期更新)-CSDN博客 一、概述         在三维模型处理过程中,精细化处理(subdivision)是一个

【SPOJ】【AGGRCOW】

总结:函数之间存在依赖。  然后一处修改了但是忘记修改另外的一处了。。。 #include <iostream>#include <cstring>#include <cmath>#include <queue>#include <stack>#include <list>#include <map>#include <set>#include <string>#inclu

Dominant Indices【模板】长链剖分

~~~~~      Dominant Indices ~~~~~      总题单链接 对比重链剖分和长链剖分 ~~~~~      什么是重链剖分:根据子树的大小将树拆成多条互不相交的链。 ~~~~~      什么是长链剖分:根据字数的深度将树拆成多条互不相交的链。 ~~~~~      重链剖分中的重儿子:子树大小最大的儿子。 ~~~~~      长链剖分中的重儿子: