树链剖分是一个很固定的套路 一般用来解决树上两点之间的路径更改与查询
思想是将一棵树分成不想交的几条链 并且由于dfs的顺序性 给每条链上的点或边标的号必定是连着的 那么每两个点之间的路径都可以拆成几条链 那么就是对一群区间进行更改 这时候基本是用线段树进行logn的操作
做了三道基础题 都属于比较好想的 也就是线段树比较麻烦 需要写相当长一段时间...
HDU 3966
给出一棵树的连接状况和边的大小 每次可以对a-b的路径的边的权值取反 或者改变指定边的值 或者求a-b路径的最大值
每次取反 最大值就是原最小值*-1 这样维护下去就好
POJ 3237
给出一棵树的连接状况和点的初始值 每次对a-b的路径上的点权进行加减 询问单点大小
树状数组会超时 只能用线段树...需要注意的是点权和边权在树链剖分的时候会有一点不同 例如 u == v 是否return 等
HYSBZ 2243
总觉得以前见过的样子..
给出一棵树的连接状况和边的初始颜色 每次可以对a-b的路径上的边进行更改颜色
最后求a-b路径上的颜色段个数
可以由线段树的本质来看 每个区间的两个子区间 都是从这个线段树一分为2
那么 一个区间内有多少个颜色段数 就等于他的两个子区间的颜色加起来 如果子区间相邻的点颜色相同 那么久减去一
可以在tr数组中记录这个区间的mlmr 即中点两边的点的颜色
每次记录下来前一条链的尾颜色 和当前链的头颜色进行对比 如果相同 就减一
最后当f1 == f2的时候 要同时对比ys1和ys2
交换uv的时候 ys1和ys2也需要交换
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
#define L long long
vector<int >q[100050];
int p[100050];
int fp[100050];
int fa[100050];
int son[100050];
int deep[100050];
int top[100050];
int num[100050];
int n , m , pp;
int pos;
void init(){
for(int i= 1;i<=n;i++){
q[i].clear();
}
memset(son , -1 ,sizeof(son));
pos = 0;
}
int in[100050];
void dfs(int u , int pre , int d){
deep[u] = d;
fa[u] = pre;
num[u] = 1;
for(int i = 0;i<q[u].size();i++){
int v = q[u][i];
if(v != pre){
dfs(v,u,d+1);
num[u] += num[v];
if(son[u] == -1 || num[v] > num[son[u]]){
son[u] = v;
}
}
}
}
void dfs2(int u , int zx){
top[u] = zx;
p[u] = pos ++;
fp[pos - 1] = u;
if(son[u] == -1){
return ;
}
dfs2(son[u],zx);
for(int i = 0;i<q[u].size();i++){
int v = q[u][i];
if(v != fa[u] && v != son[u]){
dfs2(v,v);
}
}
}
/**
线段树 1求一个区间内有多少个颜色 2求一个点的颜色
2直接写查询
1记录这个区间的 中间的两个的颜色
*/
struct node{
int l,r;
int ml;
int mr;
int ll ;
int rr ;
int mark;
int d;
}tr[100050 * 4];
void pushup(int i){
if(tr[i].l == tr[i].r)
return ;
tr[i].ll = tr[i<<1].ll;
tr[i].rr = tr[(i<<1)|1].rr ;
tr[i].ml = tr[i<<1].rr;
tr[i].mr = tr[(i<<1)|1].ll ;
tr[i].d = tr[i<<1].d + tr[(i<<1)|1].d ;
if(tr[i<<1].rr == tr[(i<<1)|1].ll)
tr[i].d -- ;
}
void pushdown(int i){
if(tr[i].l == tr[i].r)return ;
if(tr[i].mark != 0){
tr[i<<1].mark = tr[(i<<1)|1].mark = tr[i].mark ;
tr[i<<1].ll = tr[i<<1].rr = tr[i<<1].ml = tr[i<<1].mr = tr[i].mark;
tr[(i<<1)|1].ll = tr[(i<<1)|1].rr = tr[(i<<1)|1].ml = tr[(i<<1)|1].mr = tr[i].mark;
tr[i<<1].d= tr[(i<<1)|1].d = 1;
tr[i].mark = 0;
}
}
void crea(int i , int l , int r){
tr[i].l = l ;
tr[i].r = r;
tr[i].ml = tr[i].mr = tr[i].ll = tr[i].rr = tr[i].mark = 0;
if(l == r){
tr[i].ml = tr[i].mr = tr[i].ll = tr[i].rr = in[fp[l]];
tr[i].d = 1;
return ;
}
int mid = (l + r )/ 2;
crea(i<<1,l,mid);
crea((i<<1)|1,mid+1,r);
pushup(i);
}
int res ;
void upda(int i ,int l ,int r , int c){
if(tr[i].l ==l && r == tr[i].r){
tr[i].ml = tr[i].mr = tr[i].ll = tr[i].rr = tr[i].mark = c;
tr[i].d = 1;
return ;
}
pushdown(i);
int mid = (tr[i].l + tr[i].r) / 2;
if(r <= mid){
upda(i<<1,l,r,c);
}
else if(l > mid){
upda((i<<1)|1,l,r,c);
}
else {
upda(i<<1,l,mid,c);
upda((i<<1)|1,mid+1,r,c);
}
pushup(i);
}
int query(int i ,int l ,int r){
if(tr[i].l == l && r == tr[i].r){
return tr[i].d;
}
pushdown(i);
int mid = (tr[i].l + tr[i].r) / 2;
if(r <= mid){
return query(i<<1,l,r);
}
else if(l > mid){
return query((i<<1)|1,l,r);
}
else {
if(tr[i].ml == tr[i].mr){
return query(i<<1,l,mid) + query((i<<1)|1,mid+1,r) - 1;
}
else {
return query(i<<1,l,mid) + query((i<<1)|1,mid+1,r);
}
}
}
int qu2(int i ,int pos){
if(tr[i].l == tr[i].r){
return tr[i].ml ;
}
pushdown(i);
int mid = (tr[i].l + tr[i].r) / 2;
if(pos <= mid){
return qu2(i<<1,pos);
}
else {
return qu2((i<<1)|1,pos);
}
}
void did(int u , int v, int c){
int f1 = top[u];
int f2 = top[v];
while(f1 != f2){
if(deep[f1] < deep[f2]){
swap(f1,f2);
swap(u,v);
}
upda(1,p[f1],p[u],c);
u = fa[f1];
f1 = top[u];
}
if(deep[u] < deep[v]){
swap(u,v);
}
upda(1,p[v],p[u],c);
}
int slpf(int u, int v){
int ans = 0;
int f1 = top[u];
int f2 = top[v];
int ys1 = -1;
int ys2 = -1;
while(f1 != f2){
if(deep[f1] < deep[f2]){
swap(u,v);
swap(f1,f2);
swap(ys1,ys2);
}
ans += query(1,p[f1],p[u]);
if(ys1 == qu2(1,p[u])){
ans -- ;
}
ys1 = qu2(1,p[f1]);
u = fa[f1];
f1 = top[u];
//printf("%d
",ans);
}
if(deep[u] < deep[v]){
swap(u,v);
swap(ys1,ys2); /// --------
}
ans += query(1,p[v],p[u]);
if(ys1==qu2(1,p[u])){
ans -- ;
}
if(ys2==qu2(1,p[v])){
ans -- ;
}
return ans ;
}
int main(){
//freopen("in.cpp","r",stdin);
while(scanf("%d%d",&n,&pp)!=EOF){
init();
for(int i=1;i<=n;i++){
scanf("%d",&in[i]);
}
for(int i=1;i<=n-1;i++){
int u , v;
scanf("%d%d",&u,&v);
q[u].push_back(v);
q[v].push_back(u);
}
dfs(1,0,0);
dfs2(1,1);
crea(1,0,pos-1);
for(int i=1;i<=pp;i++){
char s[20];
scanf("%s",s);
if(s[0] == 'C'){
int u , v, c;
scanf("%d%d%d",&u,&v,&c);
did(u,v,c);
}
else {
int u,v;
scanf("%d%d",&u,&v);
printf("%d
",slpf(u,v));
}
}
}
}
感觉树链剖分的主要难点在于线段树的构造...
2017.3.18 很久后又做了一道树链剖分 当然LCA也可做
询问树上路径可否组成三角形 利用斐波那契的思想 由于每一条路径的len<=1e9 所以当路径的条数超过64左右的时候肯定是可以的
当小于64的时候拿出来直接暴力就可以了
树链剖分中 u与top[u] 是连着的 在这里 用a[u]存放 u到fa[u] 的边的权值
所以top[u] -> fa[top[u]] 其实是不在 u -> f1 这条链上的 但是之后会发生 u = fa[f1] 直接翻到这条边上去
所以如果top[u] -> fa[top[u]] 这个边不在路径中 是会直接发生 f1 == f2 的
所以这样记录是不会出现什么问题的 QAQ
好久不写 好麻烦...Orz
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
#define L long long
const int maxn = 100050 ;
int top[maxn] , fa[maxn] , deep[maxn] , num[maxn] , p[maxn] , fp[maxn] , son[maxn] ;
int pos ;
int n ;
int a[maxn] ;
bool can ;
vector<int > q[maxn] ;
vector<int > w[maxn] ;
vector<int > tmp ;
void init() {
pos = 1 ;
memset(son , -1 , sizeof(son)) ;
for(int i = 1 ; i <= n ; i ++ ) q[i].clear() ;
for(int i = 1 ; i <= n ; i ++ ) w[i].clear() ;
}
void dfs1(int u , int pre , int d) {
deep[u] = d ;
fa[u] = pre ;
num[u] = 1 ;
for(int i = 0 ; i < q[u].size() ; i ++ ){
int v = q[u][i] ;
if(v != pre) {
a[v] = w[u][i] ;
dfs1(v,u,d+1);
if(son[u] == -1 || num[v] > num[son[u]]) {
son[u] = v ;
}
}
}
}
void getpos(int u , int sp) {
top[u] = sp ;
p[u] = pos ++ ;
fp[p[u]] = u ;
if(son[u] == -1) return ;
getpos(son[u] , sp) ;
for(int i = 0 ; i < q[u].size() ; i ++ ){
int v = q[u][i];
if(v != son[u] && v != fa[u]) {
getpos(v,v) ;
}
}
}
void slpf(int u ,int v ) {
int f1 = top[u] , f2 = top[v] ;
int sl = 0 ;
while(f1 != f2) {
if(deep[f1] < deep[f2]) {
swap(f1 , f2) ;
swap(u , v) ;
}
sl += ( p[u] - p[f1] + 1) ;
if(sl > 65) {
can = false ;
return ;
}
else {
for(int i = p[f1] ; i <= p[u] ; i ++ ){
tmp.push_back(a[fp[i]]) ;
}
}
u = fa[f1] ;
f1 = top[u] ;
}
if(u == v) return ;
if(deep[u] > deep[v]) swap(u , v) ;
sl += (p[v] - p[son[u]] + 1) ;
if(sl > 65) {
can = false ;
return ;
}
for(int i = p[son[u]] ; i <= p[v] ; i ++ ){
tmp.push_back(a[fp[i]]) ;
}
}
int main(){
while(scanf("%d" , &n) != EOF) {
init() ;
for(int i = 1 ; i < n ; i ++ ){
int u , v , c ;
scanf("%d%d%d",&u,&v,&c) ;
q[u].push_back(v) ;
q[v].push_back(u) ;
w[u].push_back(c) ;
w[v].push_back(c) ;
}
dfs1(1,0,0) ;
getpos(1,1) ;
a[1] = -9999999 ;
int query ;
scanf("%d",&query) ;
for(int i = 1 ; i <= query ; i ++ ){
int u , v ;
scanf("%d%d",&u,&v) ;
tmp.clear() ;
can = true ;
slpf(u , v) ;
if(can == false) {
printf("Yes
") ;
}
else {
sort(tmp.begin() , tmp.end()) ;
bool ok = false ;
if(tmp.size() < 3) {
}
else {
for(int j = 2 ; j < tmp.size() ; j ++ ){
int aa = tmp[j-2] ;
int bb = tmp[j-1] ;
int cc = tmp[j] ;
if(aa + bb > cc) {
ok=true;
break ;
}
}
}
if(ok)printf("Yes
");
else printf("No
") ;
}
}
}
}