和平常的树链剖分维护边权不同的地方在于对线段树的要求较高
NEGATE
反转区间,也就是a - b 内所有的边权取相反数
而Query询问是最大值,所以也就是维护可取反区间的最大值问题
需要维护的值是区间最大值,区间最小值(反转取件后交换其值),lazy标记(优化加速,标记完全反转最大区间)
int rmax[maxn<<2],rmin[maxn<<2],lazy[maxn<<2];
对应线段树的push_up和push_down操作也就很稳了(就是维护那几个值)
void pup(int rt)
{
rmax[rt] = max(rmax[rs] , rmax[ls]);
rmin[rt] = min(rmin[rs] , rmin[ls]);
}
void pdown(int rt)
{
if(lazy[rt])
{
rmax[ls] = -rmax[ls];
rmin[ls] = -rmin[ls];
swap(rmax[ls],rmin[ls]);
rmax[rs] = -rmax[rs];
rmin[rs] = -rmin[rs];
swap(rmax[rs],rmin[rs]);
lazy[ls] ^= 1;
lazy[rs] ^= 1;
lazy[rt] = 0;
}
}
有一个要注意的地方就是本题有一个点边权更新问题,需要把lazy标记清空一下
好了其他的就是模板问题了
树链做到这基础的的就差不多了,自我感觉还比较良好——嘿嘿嘿心态嘛
/*
https://vjudge.net/contest/251031#problem/F 像是经典的树链剖分,用一下模板
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define lson rt<<1,left,mid
#define rson rt<<1|1,mid+1,right
#define ls rt<<1
#define rs rt<<1|1
#define mid ((left + right) >> 1)
#define inf (1 << 28)
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 1e3;
int n,m,p;
int V[maxn];
//邻接表
struct node{
int to,pre;
}e[maxn << 1];
struct road{
int x,y,v;
}r[maxn<<1];
int id[maxn],cnt;
//线段树
int rmax[maxn<<2],rmin[maxn<<2],lazy[maxn<<2];
//dfs1
int siz[maxn],dep[maxn],fa[maxn],son[maxn];
//dfs2
int top[maxn],num_id[maxn],id_num[maxn];
int tot;
void init()
{
memset(id,-1,sizeof(id));
memset(son,0,sizeof(son));
cnt = tot = 0;
}
void add(int from,int to)
{
e[cnt].to = to;
e[cnt].pre = id[from];
id[from] = cnt++;
}
void dfs1(int now,int f,int depth)
{
siz[now] = 1;
fa[now] = f;
dep[now] = depth; for(int i = id[now];~i;i = e[i].pre)
{
int to = e[i].to;
if(to != f)
{
dfs1(to,now,depth+1);
siz[now] += siz[to];
if(siz[to] > siz[son[now]])
son[now] = to;
}
}
}
void dfs2(int now,int rt)
{
top[now] = rt;
num_id[now] = ++tot;
id_num[tot] = now; if(!son[now]) return; dfs2(son[now],rt); for(int i = id[now];~i;i = e[i].pre)
{
int to = e[i].to;
if(to != son[now] && to != fa[now])
{
dfs2(to,to);
}
}
}
void pup(int rt)
{
rmax[rt] = max(rmax[rs] , rmax[ls]);
rmin[rt] = min(rmin[rs] , rmin[ls]);
}
void pdown(int rt)
{
if(lazy[rt])
{
rmax[ls] = -rmax[ls];
rmin[ls] = -rmin[ls];
swap(rmax[ls],rmin[ls]);
rmax[rs] = -rmax[rs];
rmin[rs] = -rmin[rs];
swap(rmax[rs],rmin[rs]);
lazy[ls] ^= 1;
lazy[rs] ^= 1;
lazy[rt] = 0;
}
}
void build(int rt,int left,int right)
{
lazy[rt] = 0;
if(left == right)
{
rmax[rt] = V[id_num[left]];
rmin[rt] = V[id_num[left]];
return;
}
build(lson);
build(rson);
pup(rt);
}
void updata(int rt,int left,int right,int l,int r,int k)
{
if(left == l && right == r)
{
rmax[rt] = k;
rmin[rt] = k;
lazy[rt] = 0;//就算翻转了也可以清除标记了
return;
} pdown(rt); if(r <= mid)
updata(lson,l,r,k);
else if(l > mid)
updata(rson,l,r,k);
else
{
updata(lson,l,mid,k);
updata(rson,mid+1,r,k);
} pup(rt);
}
void ne_updata(int rt,int left,int right,int l,int r)
{
if(l <= left && right <= r)
{
lazy[rt] ^= 1;
rmax[rt] = -rmax[rt];
rmin[rt] = -rmin[rt];
swap(rmax[rt],rmin[rt]);
//cout<<rmax[rt]<<" "<<rmin[rt]<<endl;
return;
}
pdown(rt); if(l <= mid)
ne_updata(lson,l,r);
if(r > mid)
ne_updata(rson,l,r); pup(rt);
}
void updata_lca(int x,int y)
{
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]])
swap(x,y);
ne_updata(1,1,tot,num_id[top[x]],num_id[x]);
x = fa[top[x]];
}
if(x == y)return;
if(dep[x] < dep[y])
{
swap(x,y);
}
ne_updata(1,1,tot,num_id[son[y]],num_id[x]);
return ;
}
int query(int rt,int left,int right,int l,int r)
{
int res;
res = -inf;
if(l <= left && right <= r)
{
return rmax[rt];
} pdown(rt);
if(l <= mid)
{
res = max(res,query(lson,l,r));
}
if(r > mid)
{
res = max(res,query(rson,l,r));
}
return res;
}
int querty_lca(int x,int y)
{
int res;
res = -inf;
//cout<<top[x]<<" "<<top[y]<<endl;
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]])
swap(x,y);
res = max(res,query(1,1,tot,num_id[top[x]],num_id[x]));
x = fa[top[x]];
}
if(x == y)return res;
if(dep[x] < dep[y])
{
swap(x,y);
}
res = max(res,query(1,1,tot,num_id[son[y]],num_id[x]));
return res;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
init();
int from,to,cost;
for(int i=1;i<=n-1;i++)
{
scanf("%d%d%d",&from,&to,&cost);
r[i].x = from;
r[i].y = to;
r[i].v = cost;
add(from,to);
add(to,from);
} dfs1(1,0,1);
dfs2(1,1);
for(int i=1;i<=n;++i)
{
if(dep[r[i].x] < dep[r[i].y])
swap(r[i].x,r[i].y);
V[r[i].x] = r[i].v;
}
build(1,1,tot);
//cout<<sum[4]<<" "<<sum[5]<<" "<<sum[6]<<" "<<sum[7]<<endl;
char op[10];
int x,y,z;
while(1)
{
scanf("%s",op);
if(op[0] == 'Q'){
scanf("%d%d",&x,&y);
printf("%d\n",querty_lca(x,y));
}
else if(op[0] == 'C')
{
scanf("%d%d",&x,&z);
updata(1,1,tot,num_id[r[x].x],num_id[r[x].x],z);
}
else if(op[0] == 'N')
{
scanf("%d%d",&x,&y);
updata_lca(x,y);
}
else
{
break;
}
}
}
return 0;
}
加油吧!有生活,有代码,不迷失,不深陷,体验生活,享受快乐!
[kuangbin]树链剖分 C - Tree的更多相关文章
-
【POJ3237】【树链剖分】Tree
Description You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edg ...
-
[kuangbin]树链剖分 D - 染色
https://vjudge.net/contest/251031#problem/Dhttps://blog.csdn.net/kirito_acmer/article/details/512019 ...
-
[kuangbin]树链剖分A - Aragorn&#39;s Story
比较水的题了,比模板题还要简单一点 理解了这个结构,自己打出来的,但是小错误还是很多,越来越熟练吧希望 错误函数updata,updata_lca,query||错误地方区间往下递归的时候是left ...
-
POJ 3237 Tree (树链剖分)
Tree Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 2825 Accepted: 769 Description ...
-
Query on a tree——树链剖分整理
树链剖分整理 树链剖分就是把树拆成一系列链,然后用数据结构对链进行维护. 通常的剖分方法是轻重链剖分,所谓轻重链就是对于节点u的所有子结点v,size[v]最大的v与u的边是重边,其它边是轻边,其中s ...
-
【BZOJ-4353】Play with tree 树链剖分
4353: Play with tree Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 31 Solved: 19[Submit][Status][ ...
-
Codeforces Round #329 (Div. 2) D. Happy Tree Party LCA/树链剖分
D. Happy Tree Party Bogdan has a birthday today and mom gave him a tree consisting of n vertecie ...
-
【POJ3237】Tree(树链剖分)
题意:在一棵N个节点,有边权的树上维护以下操作: 1:单边修改,将第X条边的边权修改成Y 2:区间取反,将点X与Y在树上路径中的所有边边权取反 3:区间询问最大值,询问X到Y树上路径中边权最大值 n& ...
-
HDU 4718 The LCIS on the Tree(树链剖分)
Problem Description For a sequence S1, S2, ... , SN, and a pair of integers (i, j), if 1 <= i < ...
随机推荐
-
Echarts 动态折线图
<script src="http://echarts.baidu.com/build/dist/echarts-all.js"></script>< ...
-
CCNP第二天 帧中继综合实验
实验题如图所示: 要求全网可达 R5为帧中继交换机 R6 和 R1之间为快速以太网接口 所使用的拓扑为CCNA标准版拓扑图,如下所示: -------------------------------- ...
-
Application.StartupPath同System.Environment.CurrentDirectory区别
System.Windows.Forms.Application.StartupPath:获取启动了应用程序的可执行文件的路径,不包括可执行文件的名称. System.Environment.Curr ...
-
【转】cocos2d-x 模仿计时器效果,动态增加分数&mdash;&mdash;2013-08-25 16
http://www.cocos2dev.com/?p=90 游戏中要用到分数是动态增加的,而不是瞬间加上去的. bool HelloWorld::init() { if ( !CCLayer::in ...
-
C++开源小贱鸡(simsimi api)
小贱鸡 这是一个基于Qt C++的跨平台聊天软件,源于群里面玩这个的很多. 你需要一个Qt环境编译程序以便使用. 下载:http://pan.baidu.com/s/1gdnDgC7 项目地址:htt ...
-
shell,python获取当前路径(脚本的当前路径) (aso项目记录)
一.shell获取脚本当前路径 cur_dir=$(cd "$(dirname "$0")"; pwd) #获取当前脚本的绝对路径,参数$0是当前脚本对象 等 ...
-
pycharm修改快捷键
1.keymap 2.找到需要修改的功能 3.鼠标右键选择——选择“add keyboard shortcut” 4.直接按需要设置的快捷键位,如F6 5.确定
-
UI控件Telerik UI for WinForms发布R1 2019|附下载
Telerik UI for WinForms拥有适用Windows Forms的110多个令人惊叹的UI控件.所有的UI for WinForms控件都具有完整的主题支持,可以轻松地帮助开发人员在桌 ...
-
APPium-Xpath,swipe练习
写自动化测试,实现 滚动到 口碑最佳 部分,并且打印出所有 口碑最佳 部分的5个应用名称 # coding:utf-8from appium import webdriverimport time d ...
-
asp.net导出excel 问题及服务器的部署dcom组件配置
一.服务器上没有装office 如果要用MS的,这个问题基本不用考虑,只有安装才能解决,没有其它办法! (即使有牛人弄出来 了,估计也是给自己找麻烦) 不过,我只在服务器上装了一个2003精简版, 我 ...