CF916E Jamie and Tree 解题报告
CF916E Jamie and Tree
题意翻译
有一棵\(n\)个节点的有根树,标号为\(1-n\),你需要维护一下三种操作
1.给定一个点\(v\),将整颗树的根变为\(v\)
2.给定两个点\(u, v\),将\(lca(u, v)\)所在的子树都加上\(x\)
3.给定一个点\(v\),你需要回答以\(v\)所在的子树的权值和
输入输出格式
输入格式:
The first line of input contains two space-separated integers \(n\) and \(q\) \((1<=n<=10^{5},1<=q<=10^{5})\) — the number of vertices in the tree and the number of queries to process respectively.
The second line contains \(n\) space-separated integers\(a_{1},a_{2},...,a_{n}\)(\(-10^{8}<=a_{i}<=10^{8}\)) — initial values of the vertices.
Next \(n-1\) lines contains two space-separated integers\(u_{i},v_{i}\)(\(1<=u_{i},v_{i}<=n\)) describing edge between vertices \(u_{i}\)and \(v_{i}\)in the tree.
The following \(q\) lines describe the queries.
Each query has one of following formats depending on its type:
\(1\ v\) ( \(1<=v<=n\) ) for queries of the first type.
\(2\ u\ v\ x\) ( \(1<=u,v<=n,-10^{8}<=x<=10^{8}\) ) for queries of the second type.
\(3\ v ( 1<=v<=n )\) for queries of the third type.
All numbers in queries' descriptions are integers.
The queries must be carried out in the given order. It is guaranteed that the tree is valid.
输出格式:
For each query of the third type, output the required answer. It is guaranteed that at least one query of the third type is given by Jamie.
强制换根==分类讨论
如果在考场上比较难写就考虑暴力吧
首先介绍几点可能比较常见的
1.换根后的\(lca(u,v)\)
其实求法比较多,介绍一种
设\(z1=lca(u,root),z2=lca(v,root)\),如果\(z1==z2\),则\(lca(u,v)\)不变,否则\(lca(u,v)\)为\(z1,z2\)中深度较深的那个
2.一个点是否在某点的子树里
bool in(int x)
{
if(dfn[x]>=dfn[root]&&dfn[x]<=dfn[root]+siz[root]-1) return true;
return false;
}
对于这道题,我们在分类讨论上稍稍用一点容斥原理即可
Code:
#include <cstdio>
#define ll long long
#define ls id<<1
#define rs id<<1|1
const int N=100010;
int head[N],to[N<<1],Next[N<<1],cnt;
void add(int u,int v)
{
to[++cnt]=v;Next[cnt]=head[u];head[u]=cnt;
}
int f[N][20],dfn[N],dep[N],siz[N],ha[N],dfs_clock,root;
void dfs(int now)
{
dfn[now]=++dfs_clock;
ha[dfs_clock]=now;
siz[now]++;
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(f[now][0]!=v)
{
dep[v]=dep[now]+1;
f[v][0]=now;
dfs(v);
siz[now]+=siz[v];
}
}
}
ll sum[N<<2],lazy[N<<2],dat[N];
int n,q;
void updata(int id)
{
sum[id]=sum[ls]+sum[rs];
}
void push_down(int id,ll L,ll R)
{
if(!lazy[id]) return;
if(L!=R)
{
ll mid=L+R>>1;
sum[ls]+=(mid+1-L)*lazy[id];
sum[rs]+=(R-mid)*lazy[id];
lazy[ls]+=lazy[id];
lazy[rs]+=lazy[id];
}
lazy[id]=0;
}
void build(int id,int l,int r)
{
if(l==r)
{
sum[id]=dat[ha[l]];
return;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
updata(id);
}
void change(int id,ll l,ll r,ll L,ll R,ll delta)
{
push_down(id,L,R);
if(l==L&&r==R)
{
sum[id]+=(R+1-L)*delta;
lazy[id]+=delta;
return;
}
ll mid=L+R>>1;
if(r<=mid) change(ls,l,r,L,mid,delta);
else if(l>mid) change(rs,l,r,mid+1,R,delta);
else change(ls,l,mid,L,mid,delta),change(rs,mid+1,r,mid+1,R,delta);
updata(id);
}
ll query(int id,ll l,ll r,ll L,ll R)
{
push_down(id,L,R);
if(l==L&&r==R) return sum[id];
ll mid=L+R>>1;
if(r<=mid) return query(ls,l,r,L,mid);
else if(l>mid) return query(rs,l,r,mid+1,R);
else return query(ls,l,mid,L,mid)+query(rs,mid+1,r,mid+1,R);
}
void init()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%lld",dat+i);
for(int u,v,i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dep[1]=1;
dfs(root=1);
for(int j=1;j<=18;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
build(1,1,n);
}
void Swap(int &x,int &y)
{
int tmp=x;
x=y;
y=tmp;
}
int LCA0(int x,int y)//原树的LCA
{
if(dep[x]<dep[y]) Swap(x,y);
for(int i=18;~i;i--)
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y) return x;
for(int i=18;~i;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
int LCA(int x,int y)//换根后的LCA
{
int z1=LCA0(x,root),z2=LCA0(y,root);
if(z1==z2) return LCA0(x,y);
else return dep[z1]>dep[z2]?z1:z2;
}
bool in(int x)//询问x是否在以root为根的子树里
{
if(dfn[x]>=dfn[root]&&dfn[x]<=dfn[root]+siz[root]-1) return true;
return false;
}
int querys(int x)//询问根到x位置上x的那个儿子
{
int y=root;
for(int i=18;~i;i--)
if(dep[f[y][i]]>dep[x])
y=f[y][i];
return y;
}
void modify(int x,ll delta)//给以x为根的子树加上delta
{
if(in(x))
{
if(x!=root) change(1,dfn[x],dfn[x]+siz[x]-1,1,n,delta);
else change(1,1,n,1,n,delta);
return;
}
int son=querys(x);
if(f[son][0]==x)
{
change(1,1,n,1,n,delta);
change(1,dfn[son],dfn[son]+siz[son]-1,1,n,-delta);
}
else
change(1,dfn[x],dfn[x]+siz[x]-1,1,n,delta);
}
ll ask(int x)//询问新根下子树权值和
{
if(in(x))
{
if(x!=root) return query(1,dfn[x],dfn[x]+siz[x]-1,1,n);
return query(1,1,n,1,n);
}
int son=querys(x);
ll ans=0;
if(f[son][0]==x)
{
ans+=query(1,1,n,1,n);
ans-=query(1,dfn[son],dfn[son]+siz[son]-1,1,n);
}
else
ans=query(1,dfn[x],dfn[x]+siz[x]-1,1,n);
return ans;
}
void work()
{
ll x;
for(int opt,u,v,i=1;i<=q;i++)
{
scanf("%d",&opt);
if(opt==1)
{
scanf("%d",&u);
root=u;
}
else if(opt==2)
{
scanf("%d%d%lld",&u,&v,&x);
modify(LCA(u,v),x);
}
else
{
scanf("%d",&u);
printf("%lld\n",ask(u));
}
}
}
int main()
{
init();
work();
return 0;
}
2018.7.31
最新文章
- PL/SQL连接错误:ora-12705:cannot access NLS data files or invalid environment specified
- 编写更加稳定/可读的javascript代码
- 时间函数 time.h 详解
- PHPExcel操作sae的storage上的文件
- hibernate hbm2ddl auto 不能创建表的问题
- 我的第一个Spring程序
- php批量发送短信或邮件的方案
- 获取文件CRC和MD5
- ExtJS 4 MVC架构讲解
- 【HDOJ】1510 White Rectangles
- 为什么推荐Zookeeper作注册中心
- PHP字节格式化
- 理解Node.js(译文)
- Unity Shader入门教程(四)反射光斑的实现
- 《程序设计语言&mdash;&mdash;实践之路【PDF】下载
- rk3128 通过串口控制 GPIO
- Channels实现扫码登录
- 学习Emmet
- MFC中显示图像的放大、缩小、移动功能
- 我的Python升级打怪之路【五】:Python模块