【codeforces】482E. ELCA 动态树

2024-09-05 14:32
文章标签 动态 codeforces 482e elca

本文主要是介绍【codeforces】482E. ELCA 动态树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：【codeforces】482E. ELCA


题目大意：给一棵有根树，树根为1，每个节点有权值s[v]，q次操作，每次要么将以v为根的子树接到u下，要么令s[v]=t，每次操作以后，输出等概率选择两个点i,j（i可以等于$）后权值的期望，权值即s[{lca(i,j)}]值。


题目分析：写了两天啊啊啊啊！！！终于搞出来了。。。思考这题算法的时候总感觉脑子不够用啊= =于是好不容易AC了一次就再写了一发。。

这题一看就知道是动态树问题，但关键的是怎么转化，比较好的方法是每个节点x保存以这个节点为根结点的子树中LCA为x的路径种数，x的子树大小tree_siz，x在splay中不包括splay树中右儿子tree_siz的siz，这样在处理的过程中改变access函数，每次access一定是将真实树中的树边扩充为splay边，然后很巧妙的就可以转化为路径求和问题。具体只能见代码= =我真的描述不清楚。。。

1.注意cut以及link操作是怎么执行的。

2.注意tree_siz只与真实树有关，所以除了cut及link涉及的修改路径操作，splay的其他操作都对他没有影响。

3.注意siz只在access的时候发生变化。


代码如下：


#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;typedef long long LL ;#define rep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 50005 ;
const int MAXE = 100005 ;struct Node* null ;
struct Node {Node* c[2] ;Node* f ;LL cnt ;LL sum ;int val ;int siz ;int lazy ;int tree_siz ;inline void new_node () {sum = val = 0 ;c[0] = c[1] = f = null ;lazy = 0 ;}inline void add_siz ( int SIZE ) {if ( this == null ) return ;tree_siz += SIZE ;cnt += 2LL * siz * SIZE ;lazy += SIZE ;}inline void push_up () {sum = c[0]->sum + ( LL ) siz * val + c[1]->sum ;}inline void push_down () {if ( lazy ) {c[0]->add_siz ( lazy ) ;c[1]->add_siz ( lazy ) ;lazy = 0 ;}}inline bool is_root () {return f == null || f->c[0] != this && f->c[1] != this ;}inline void sign_down () {if ( !is_root () ) f->sign_down () ;push_down () ;}inline void setc ( Node* o , bool d ) {c[d] = o ;o->f = this ;}inline void rot ( bool d ) {Node* p = f ;Node* g = f->f ;p->setc ( c[d] , !d ) ;if ( !p->is_root () ) g->setc ( this , p == g->c[1] ) ;else f = g ;setc ( p , d ) ;p->push_up () ;}inline void splay () {sign_down () ;while ( !is_root () ) {if ( f->is_root () ) rot ( this == f->c[0] ) ;else {if ( f == f->f->c[0] ) {if ( this == f->c[0] ) f->rot ( 1 ) , rot ( 1 ) ;else rot ( 0 ) , rot ( 1 ) ;} else {if ( this == f->c[1] ) f->rot ( 0 ) , rot ( 0 ) ;else rot ( 1 ) , rot ( 0 ) ;}}}push_up () ;}inline void access () {Node* o = this ;Node* x = null ;while ( o != null ) {if ( x != null ) {while ( x->c[0] != null ) x = x->c[0] ;x->splay () ;}o->splay () ;o->siz = o->tree_siz - x->tree_siz ;//without splay_tree right_son tree_sizo->setc ( x , 1 ) ;o->push_up () ;x = o ;o = o->f ;}splay () ;}
} ;struct Edge {int v ;Edge* next ;
} ;Node pool[MAXN] ;
Node* node[MAXN] ;
Node* curN ;
Edge edge[MAXE] ;
Edge* H[MAXN] ;
Edge* curE ;
LL ans ;
int n , m ;void clear () {ans = 0 ;curE = edge ;curN = pool ;null = curN ++ ;null->new_node () ;null->cnt = null->tree_siz = null->siz = 0 ;clr ( H , 0 ) ;
}void addedge ( int u , int v ) {curE->v = v ;curE->next = H[u] ;H[u] = curE ++ ;
}void dfs ( int u ) {node[u]->cnt = node[u]->tree_siz = 1 ;for ( Edge* e = H[u] ; e ; e = e->next ) {int v = e->v ;dfs ( v ) ;node[u]->cnt += 2LL * node[u]->tree_siz * node[v]->tree_siz ;node[u]->tree_siz += node[v]->tree_siz ;}ans += node[u]->cnt * node[u]->val ;//calculate init ansnode[u]->siz = node[u]->tree_siz ;
}void solve () {int x , y ;char op[2] ;double tot = ( double ) n * n ;clear () ;For ( i , 1 , n ) {node[i] = curN ++ ;node[i]->new_node () ;}For ( i , 2 , n ) {scanf ( "%d" , &x ) ;addedge ( x , i ) ;node[i]->f = node[x] ;}For ( i , 1 , n ) scanf ( "%d" , &node[i]->val ) ;dfs ( 1 ) ;printf ( "%.10f\n" , ans / tot ) ;scanf ( "%d" , &m ) ;while ( m -- ) {scanf ( "%s%d%d" , op , &x , &y ) ;if ( op[0] == 'P' ) {node[y]->access () ;node[x]->splay () ;if ( node[x]->f == null ) swap ( x , y ) ;//cutnode[x]->access () ;Node* o = node[x]->c[0] ;ans -= 2LL * o->sum * node[x]->tree_siz ;o->add_siz ( -node[x]->tree_siz ) ;node[x]->c[0]->f = null ;node[x]->c[0] = null ;node[x]->push_up () ;o->push_up () ;//linknode[y]->access () ;ans += 2LL * node[y]->sum * node[x]->tree_siz ;node[y]->add_siz ( node[x]->tree_siz ) ;node[y]->push_up () ;node[x]->f = node[y] ;} else {node[x]->access () ;ans += node[x]->cnt * ( y - node[x]->val ) ;node[x]->val = y ;node[x]->push_up () ;}printf ( "%.10f\n" , ans / tot ) ;}
}int main () {while ( ~scanf ( "%d" , &n ) ) solve () ;return 0 ;
}


压缩后代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define clr(a,x) memset(a,x,sizeof a)
const int MAXN=50005;
const int MAXE=100005;
struct Node *null;
struct Node{Node *c[2],*f;LL cnt,sum;int val,siz,lazy,tree_siz;inline void new_node(){sum=val=lazy=0,c[0]=c[1]=f=null;}inline void add_siz(int SIZE){if(this==null)return;tree_siz+=SIZE;cnt+=2LL*siz*SIZE;lazy+=SIZE;}inline void up(){sum=c[0]->sum+(LL)siz*val+c[1]->sum;}inline void down(){if(lazy)c[0]->add_siz(lazy),c[1]->add_siz(lazy),lazy=0;}inline bool is_root(){return f==null||f->c[0]!=this&&f->c[1]!=this;}inline void sign_down(){if(!is_root())f->sign_down();down();}inline void setc(Node *o,bool d){c[d]=o,o->f=this;}inline void rot(bool d){Node *p=f,*g=f->f;p->setc(c[d],!d);if(!p->is_root())g->setc(this,p==g->c[1]);else f=g;setc(p,d);p->up();}inline void splay(){for(sign_down();!is_root();){if(f->is_root())rot(this==f->c[0]);else{if(f==f->f->c[0])this==f->c[0]?f->rot(1):rot(0),rot(1);else this==f->c[1]?f->rot(0):rot(1),rot(0);}}up();}inline void access(){for(Node*o=this,*x=null;o!=null;x=o,o=o->f){if(x!=null){while(x->c[0]!=null)x=x->c[0];x->splay();}o->splay();o->siz=o->tree_siz-x->tree_siz;//withoutsplay_treeright_sontree_sizo->setc(x,1);o->up();}splay();}
}pool[MAXN],*node[MAXN],*curN;;
struct Edge{int v;Edge *next;
}edge[MAXE],*H[MAXN],*curE;
LL ans;
int n,m;
void init(){ans=0;curE=edge;curN=pool;null=curN++;null->new_node();null->cnt=null->tree_siz=null->siz=0;clr(H,0);
}
void addedge(int u,int v){curE->v=v;curE->next=H[u];H[u]=curE++;
}
void dfs(int u){node[u]->cnt=node[u]->tree_siz=1;for(Edge *e=H[u];e;e=e->next){int v=e->v;dfs(v);node[u]->cnt+=2LL*node[u]->tree_siz*node[v]->tree_siz;node[u]->tree_siz+=node[v]->tree_siz;}ans+=node[u]->cnt*node[u]->val;//calculateinitansnode[u]->siz=node[u]->tree_siz;
}
void solve(){int x,y,i;char op[2];double tot=(double)n*n;init();for(i=1;i<=n;++i){node[i]=curN++;node[i]->new_node();}for(i=2;i<=n;++i){scanf("%d",&x);addedge(x,i);node[i]->f=node[x];}for(i=1;i<=n;++i)scanf("%d",&node[i]->val);dfs(1);printf("%.10f\n",ans/tot);scanf("%d",&m);while(m--){scanf("%s%d%d",op,&x,&y);if(op[0]=='P'){node[y]->access();node[x]->splay();if(node[x]->f==null)swap(x,y);//cutnode[x]->access();Node *o=node[x]->c[0];ans-=2LL*o->sum*node[x]->tree_siz;o->add_siz(-node[x]->tree_siz);node[x]->c[0]->f=null;node[x]->c[0]=null;node[x]->up();o->up();//linknode[y]->access();ans+=2LL*node[y]->sum*node[x]->tree_siz;node[y]->add_siz(node[x]->tree_siz);node[y]->up();node[x]->f=node[y];}else{node[x]->access();ans+=node[x]->cnt*(y-node[x]->val);node[x]->val=y;node[x]->up();}printf("%.10f\n",ans/tot);}
}
int main(){while(~scanf("%d",&n))solve();return 0;
}



这篇关于【codeforces】482E. ELCA 动态树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1139225。

相关文章

VUE动态绑定class类的三种常用方式及适用场景详解

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式（对象添加：情景一）2.动态添加一个class样式（字符串添加：情
阅读更多...
SpringCloud配置动态更新原理解析

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R
阅读更多...
如何用Python绘制简易动态圣诞树

如何用Python绘制简易动态圣诞树

《如何用Python绘制简易动态圣诞树》这篇文章主要给大家介绍了关于如何用Python绘制简易动态圣诞树,文中讲解了如何通过编写代码来实现特定的效果,包括代码的编写技巧和效果的展示,需要的朋友可以参考... 目录代码：效果：总结 代码：import randomimport timefrom math
阅读更多...
Java中JSON字符串反序列化(动态泛型)

Java中JSON字符串反序列化(动态泛型)

《Java中JSON字符串反序列化(动态泛型)》文章讨论了在定时任务中使用反射调用目标对象时处理动态参数的问题,通过将方法参数存储为JSON字符串并进行反序列化,可以实现动态调用,然而,这种方式容易导... 需求：定时任务扫描，反射调用目标对象，但是，方法的传参不是固定的。方案一：将方法参数存成jsON字
阅读更多...
.NET利用C#字节流动态操作Excel文件

.NET利用C#字节流动态操作Excel文件

《.NET利用C#字节流动态操作Excel文件》在.NET开发中,通过字节流动态操作Excel文件提供了一种高效且灵活的方式处理数据,本文将演示如何在.NET平台使用C#通过字节流创建,读取,编辑及保... 目录用C#创建并保存Excel工作簿为字节流用C#通过字节流直接读取Excel文件数据用C#通过字节
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
Codeforces Round #261 (Div. 2)小记

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件，我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m
阅读更多...
Codeforces Beta Round #47 C凸包 （最终写法）

Codeforces Beta Round #47 C凸包 （最终写法）

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2