SPOJ 375(树链剖分)
2024-10-15 23:41:28
题目连接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28982#problem/I
题意:一棵包含N 个结点的树,每条边都有一个权值,要求模拟两种操作:
(1)改变某条边的权值。
(2)询问U,V 之间的路径中权值最大的边。
树链剖分裸题,入门资料:http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 10007
#define inf 0x3f3f3f3f
#define N 10010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
struct edge
{
int to,next;
edge(){}
edge(int to,int next):to(to),next(next){}
}e[N<<];
int head[N<<],tot;
int top[N];//top[v]表示v所在的重链的顶端节点
int fa[N];//父亲节点
int dep[N];//深度
int sz[N];//si[v]表示以v为根节点的子树的节点数
int son[N];//重儿子
int p[N];//p[v]表示v与其父亲节点的连边在线段树中的位置
int fp[N];//与p数组相反
int pos;//所有链构成的线段树总长度
int mx[N<<],E[N][];
void addedge(int u,int v)
{
e[tot]=edge(v,head[u]);
head[u]=tot++;
}
void init()
{
tot=;FILL(head,-);
pos=;FILL(son,-);
}
void dfs(int u,int f,int d)
{
sz[u]=;dep[u]=d;fa[u]=f;
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if(v==f)continue;
dfs(v,u,d+);
sz[u]+=sz[v];
if(son[u]==-||sz[son[u]]<sz[v])son[u]=v;
}
}
void getpos(int u,int sp)
{
top[u]=sp;
p[u]=++pos;
fp[pos]=u;
if(son[u]==-)return;
getpos(son[u],sp);
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if(v!=son[u]&&v!=fa[u])
{
getpos(v,v);
}
}
}
int Pushup(int rt)
{
mx[rt]=max(mx[rt<<],mx[rt<<|]);
}
void update(int id,int c,int l,int r,int rt)
{
if(l==r)
{
mx[rt]=c;
return;
}
int m=(l+r)>>;
if(id<=m)update(id,c,lson);
else update(id,c,rson);
Pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
return mx[rt];
int m=(l+r)>>;
int res=-inf;
if(L<=m)res=max(res,query(L,R,lson));
if(m<R)res=max(res,query(L,R,rson));
return res;
}
int lca(int u,int v)
{
int fu=top[u],fv=top[v];
int res=-inf;
while(fu!=fv)
{
if(dep[fu]<dep[fv])
{
swap(fu,fv);swap(u,v);
}
res=max(res,query(p[fu],p[u],,pos,));
u=fa[fu];fu=top[u];
}
if(u==v)return res;
if(dep[u]>dep[v])swap(u,v);
return max(res,query(p[son[u]],p[v],,pos,));
}
int main()
{
int T,n,u,v;
scanf("%d",&T);
while(T--)
{
init();
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d%d%d",&E[i][],&E[i][],&E[i][]);
addedge(E[i][],E[i][]);
addedge(E[i][],E[i][]);
}
dfs(,,);
getpos(,);
for(int i=;i<n;i++)
{
if(dep[E[i][]]>dep[E[i][]])
swap(E[i][],E[i][]);
update(p[E[i][]],E[i][],,pos,);
}
char op[];
while()
{
scanf("%s",op);
if(op[]=='D')break;
scanf("%d%d",&u,&v);
if(op[]=='Q')
printf("%d\n",lca(u,v));
else update(p[E[u][]],v,,pos,);
}
}
}
最新文章
- 大白话讲解Promise(三)搞懂jquery中的Promise
- AndroidStudio中activity实现去掉标题栏
- 海量数据相似度计算之simhash短文本查找
- JQuery上传插件uploadify优化
- 手把手教你从 Core Data 迁移到 Realm
- 小笔记:Timer定时间隔时间操作
- Mac下安装最新版本的Graphviz
- Activiti reassign task to another user
- JQuery is()与hasClass()方法的对比
- PHP实现视频文件上传完整实例
- C语言 &#183; 字串逆序
- L1-038 新世界
- OK335xS pwm device register hacking
- VC2008 类型重定义的问题
- 机器大数据也离不开Hadoop
- JAVA 导出 Excel, JS 导出 Excel
- 解决Slave SQL线程Waiting for binlog lock
- poj 1611 The Suspects(第一道并查集)
- POJ1064 Cable master 【二分找最大值】
- css 更换浏览器 默认图标