题目大意:
给出一棵树,点上有点权
有两种询问,询问两点之间树链上的点权和,询问两点之间树链上最大点权
点数<=30000,询问树<=200000
最裸的动态树,操作少,维护的值简单
{int y=fa(x),z=fa(y);if(lc(z)==y)lc(z)=x;else if(rc(z)==y)rc(z)=x;fa(x)=z;fa(rc(x))=y;lc(y)=rc(x);rc(x)=y;fa(y)=x;Update(y);}{int y=fa(x),z=fa(y);if(lc(z)==y)lc(z)=x;else if(rc(z)==y) rc(z)=x;fa(x)=z;fa(lc(x))=y;rc(y)=lc(x);lc(x)=y;fa(y)=x;Update(y);}void
Splay(int x){for(int y,z;!isRoot(x);){y=fa(x);z=fa(y);if(isRoot(y))if(lc(y)==x)Zig(x);else Zag(x);elseif(lc(z)==y)if(lc(y)==x)Zig(y),Zig(x);else Zag(x),Zig(x);elseif(lc(y)==x)Zig(x),Zag(x);else Zag(y),Zag(x);}Update(x);}void DFS(int u,int f){key(u)=w[u];erep(i,e,h[u])if(e[i].node!=f)DFS(e[i].node,u),fa(e[i].node)=u;}void
Init(){int a,b;scanf("%d",&n);rep(i,1,n-1){scanf("%d%d",&a,&b);add(a,b);add(b,a);}rep(i,1,n)scanf("%d",w+i);key(0)=Max(0)=-oo;DFS(1,0);}inline void Expose(int x){int y;for(y=0;x;x=fa(x)){Splay(x);rc(x)=y;Update(x);y=x;}}inline void Change(int x,int y){key(x)=y;Splay(x);}inline
int Qmax(int x,int y){Expose(y);for(y=0;x;x=fa(x)){Splay(x);if(!fa(x))return max(key(x),max(Max(rc(x)),Max(y)));rc(x)=y;Update(x);y=x;}}inline int Qsum(int x,int y){Expose(y);for(y=0;x;x=fa(x)){Splay(x);if(!fa(x))return sum(rc(x))+key(x)+sum(y);rc(x)=y;Update(x);y=x;}}void
Work(){char ch[10];int a,b;scanf("%d",&Q);rep(i,1,Q){scanf("%s%d%d",ch,&a,&b);if(ch[0]=='C')Change(a,b);else{if(ch[1]=='M')printf("%d\n",Qmax(a,b));else printf("%d\n",Qsum(a,b));}}}int main(){//freopen((name+in).c_str(),"r",stdin);//freopen((name+out).c_str(),"w",stdout);Init();Work();return
0;}
分享到:
相关推荐
SourceCount代码统计工具,可以统计出代码行数。方便实用,无需注册。 SourceCount代码行数统计工具
代码行数统计工具,特别好用,可以统计代码的注释行数、空行数、代码有效行数。值得拥有。 代码行数统计工具,特别好用,可以统计代码的注释行数、空行数、代码有效行数。值得拥有。
题目:分类统计字符个数COUNT_CHAR程序接收用户键入的一行字符(字符个数不超过80个,该字符串用回车符结束),
代码行统计工具CountLines.exe
Count Lines of code 统计代码行数
代码统计工具 sourcecount,很好用的统计代码工具
代码统计工具,可看新增,修改,删除行数。语言Java,html,jsp,c++等各种语言 操作是将两个不同版本的项目导入到工具中,然后点击count按钮,直接就能看结果
countlines 代码统计工具 统计代码 你想知道你一天写了多少java代码、JSP代码之类的么?下载下来看看吧,才9K,好用。
SourceCount能够轻松帮助你统计代码行数,可统计单一文件代码行数,也可以添加目录分别统计总行数。开发者必备工具。1:选择程序语言 目前支持三种类型的工程,在后期版本中将增加对HTML/JSP、HTML/ASP类工程的支持...
sourcecount 代码行统计工具,可以统计C/C++、JAVA、Basic三中言语的代码行数
很好用的代码统计工具很好用的代码统计工具很好用的代码统计工具
代码行统计,该工具能够支持C语言C++ java语言和VB语言的统计。统计的文件类型是.java文件,JSP html等则统计不到。
题目:分类统计字符个数COUNT_CHAR 2实验要求:程序接收用户键入的一行字符(字符个数不超过80个,该字符串用回车符结束),并按字母、数字、及其它字符分类计数,然后将结果存入以letter,dight,other为名的存储...
BLOG_Oracle_lhr_【优化】COUNT(1)、COUNT()、COUNT(常量)、COUNT(主键)、COUNT(ROWID)、COUNT(非空列)、COUNT(允许为空列)、COUNT(DISTINCT 列名).pdf
介绍完了COUNT(*),接下来看看COUNT(1),对于,这者到底有没有区别,上的说法众说纷纭。有的说 COUNT(*) 执时会转换成 COUNT(1) ,所
layui laypage插件如何通过ajax返回动态count值,然后重置laypage count值
每个统计的目录都会作为树结点加到树上去。当选择统计 的目录已经统计,则更新该目录。选择一个统计的目录,点del键时可删除这个统计 结点 6、单击统计结果表格的表头时,会按正反序进行排序,文件名按字母顺序...
代码行数统计工具CountLines C/C++/Java/Xml
用于CAD作图时,汇总数量,统计,制作成表格
count各列性能统计.xlsx