1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 23015  Solved: 9336
[Submit][Status][Discuss]

Description

  一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成
一些操作: I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I
II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意:从点u到点v的路径上的节点包括u和v本身

Input

  输入的第一行为一个整数n,表示节点的个数。接下来n – 1行,每行2个整数a和b,表示节点a和节点b之间有
一条边相连。接下来n行,每行一个整数,第i行的整数wi表示节点i的权值。接下来1行,为一个整数q,表示操作
的总数。接下来q行,每行一个操作,以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 
对于100%的数据,保证1<=n<=30000,0<=q<=200000;中途操作中保证每个节点的权值w在-30000到30000之间。

Output

  对于每个“QMAX”或者“QSUM”的操作,每行输出一个整数表示要求输出的结果。

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16

题意不用翻译,直接就是中文的。

我写这道题的时候感觉自己更智障了,wa了4发,怎么都不知道哪里错了,最后发现是区间查询的时候求和的初始值初始错了(黑脸)

自己的线段树的模板,还是用得顺手,树链剖分的get的两个函数是偷的学长的,学长的代码比有些博客上的写的好,嘻嘻嘻。

感谢学长给我讲了这两个函数,哈哈哈哈哈哈。

代码很认真地写了注释,线段树不理解的再去翻以前写的线段树的博客。

其他就没什么啦,开心.jpg

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll; const double PI=acos(-1.0);
const double eps=1e-;
const ll mod=1e9+;
const int inf=0x3f3f3f3f;
const int maxn=1e5+;
const int maxm=+;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 int son[maxn],siz[maxn],fa[maxn],dep[maxn],top[maxn],tip[maxn]; struct Edge{//题目的树
int to,next;
}e[maxn<<]; int tot=,cnt=,head[maxn]; void add(int u,int v)//链式前向星存树(图)
{
e[tot].to=v;
e[tot].next=head[u];
head[u]=tot++;
} //树链剖分部分
void dfs1(int u,int father)//第一遍dfs,可以得到当前节点的父亲节点,当前节点的深度,当前节点的重儿子
{
//更新dep,fa,siz数组
siz[u]=;//保存以u为根的子树节点个数
fa[u]=father;//保存爸爸
dep[u]=dep[father]+;//记录深度
for(int i=head[u];i!=-;i=e[i].next){//遍历所有和当前节点连接的节点
int v=e[i].to;
if(v==fa[u]) continue;//如果连接的是当前节点的父亲节点,则不处理
dfs1(v,u);
siz[u]+=siz[v];//直接子树节点相加,当前节点的size加上子节点的size
if(siz[v]>siz[son[u]]) son[u]=v;//如果没有设置过重节点son或者子节点v的size大于之前记录的重节点son,进行更新,保存重儿子
}
} void dfs2(int u,int tp)//第二遍dfs,将各个重节点连接成重链,轻节点连接成轻链,并且将重链(区间)用数据结构(一般是树状数组或者线段树)来维护,并且为每个节点进行编号,其实就是dfs在执行时的顺序(tip数组),以及当前节点所在链的起点(top数组)还有当前节点在树中的位置(pos)
{
tip[u]=cnt++;//保存树中每个节点剖分以后的新编号(dfs的执行顺序)
top[u]=tp;//保存当前节点所在的链的顶端节点,当前节点的起点
if(son[u]) dfs2(son[u],tp);//如果当前节点没有处在重链上,则不处理,否则就将这条重链上的所有节点都设置成起始的重节点
for(int i=head[u];i!=-;i=e[i].next){//遍历所有和当前节点连接的节点
int v=e[i].to;
if(v!=fa[u]&&son[u]!=v) dfs2(v,v);//如果连接节点不是当前节点的重节点并且也不是u的父节点,则将其的top设置成自己,进一步递归
}
} int w[maxn<<],sum[maxn<<],Max[maxn]; //线段树部分
void pushup(int rt)
{
Max[rt]=max(Max[rt<<],Max[rt<<|]);
sum[rt]=sum[rt<<]+sum[rt<<|];
} void build(int l,int r,int rt)//线段树建树
{
if(l==r){
sum[rt]=Max[rt]=w[l];
return;
} int m=(l+r)>>;
build(lson);
build(rson);
pushup(rt);
} void update(int pos,int val,int l,int r,int rt)//单点更新
{
if(l==r){
sum[rt]=Max[rt]=val;
return;
} int m=(l+r)>>;
if(pos<=m) update(pos,val,lson);
else update(pos,val,rson);
pushup(rt);
} int query_max(int L,int R,int l,int r,int rt)//区间查询最大值
{
if(L<=l&&r<=R){
return Max[rt];
} int ret=-<<;
int m=(l+r)>>;
if(L<=m) ret=max(ret,query_max(L,R,lson));
if(R> m) ret=max(ret,query_max(L,R,rson));
return ret;
} int query_sum(int L,int R,int l,int r,int rt)//区间求和
{
if(L<=l&&r<=R){
return sum[rt];
} ll ret=;
int m=(l+r)>>;
if(L<=m) ret+=query_sum(L,R,lson);
if(R> m) ret+=query_sum(L,R,rson);
return ret;
} void get_sum(int u,int v,int n)//这是最重要的,将树链和线段树联系起来
{
int ans=;
while(top[u]!=top[v]){//如果两点的top节点不相同
if(dep[top[v]]<dep[top[u]]) swap(u,v);//始终让top[v]的深度大于top[u]的,查询深度大的
ans+=query_sum(tip[top[v]],tip[v],,n,);//查询对应线段树上的区间和,通过tip数组找到对应的位置,找到线段树对应的左右区间l,r,l<=r
v=fa[top[v]];//将其更改为父亲节点
} if(dep[u]<dep[v]) swap(u,v);//如果查询的是在线段树一个完整的区间里的一部分
ans+=query_sum(tip[v],tip[u],,n,);//直接查询就可以
printf("%d\n",ans);
} void get_max(int u,int v,int n)//同上操作
{
int ans=-<<;
while(top[u]!=top[v]){
if(dep[top[v]]<dep[top[u]]) swap(u,v);
ans=max(ans,query_max(tip[top[v]],tip[v],,n,));
v=fa[top[v]];
} if(dep[u]<dep[v]) swap(u,v);
ans=max(ans,query_max(tip[v],tip[u],,n,));
printf("%d\n",ans);
} int main()
{
int n,q,a,b;
char s[];
scanf("%d",&n);
memset(head,-,sizeof(head));
for(int i=;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b);//加边
add(b,a);//加边
} dfs1(,);//第一遍dfs
dfs2(,);//第二遍dfs
for(int i=;i<=n;i++)
scanf("%d",&w[tip[i]]); build(,n,);//建树
scanf("%d",&q); while(q--){//查询
scanf("%s%d%d",s,&a,&b);
if(s[]=='M') get_max(a,b,n);
else if(s[]=='S') get_sum(a,b,n);
else update(tip[a],b,,n,);
}
}

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈。

溜了。。。】

 

最新文章

  1. linux ACL权限规划:getfacl,setfacl使用
  2. algorithm 学习之 for_each
  3. Java新集合
  4. Windows 2008 R2 Powershell 3.0
  5. web前端开发:css3实现loading
  6. 应用MVP模式写出可维护的优美Android应用
  7. Android SDK 环境变量配置(Windows)
  8. 计算机网络课程优秀备考PPT之第四章介质访问控制层(四)
  9. gcc 源代码分析-前端篇3
  10. 原来你是这样的Websocket--抓包分析
  11. sys模块和序列化模块
  12. Unity 5.X扩展编辑器之打包assetbundle
  13. Android 应用的逆向和审计
  14. Django 之 admin管理工具
  15. JaVa第二周学习总结
  16. dos.orm
  17. Exif格式分析
  18. IntelliJ IDEA for Mac(Java 语言开发的集成环境)破解版安装
  19. uniGUI for C++ builder下如何利用FastReport实现数据记录本地打印
  20. &lt;Convolutional Neural Network for Paraphrase Identification&gt;

热门文章

  1. IPad Pro 2018 &amp; sketch
  2. hibernate对单表的增删改查
  3. Java —— Reflect反射机制
  4. 你试过不用if写代码吗?
  5. Consumer [分组背包]
  6. java封装的使用
  7. TCP(二)
  8. JetbrainsCrack
  9. NGINX : 如何屏蔽未被定义的虚拟主机的访问
  10. bootstrap row 行间距