首页 > 代码库 > BZOJ 4034 树上操作(树的欧拉序列+线段树)
BZOJ 4034 树上操作(树的欧拉序列+线段树)
刷个清新的数据结构题爽一爽？
题意:
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
注意到操作3，询问x到根的路径之间点权和，容易发现这就是欧拉序列中的前缀和。
所以按照树的欧拉序列建线段树，然后操作1就变成单点修改，操作2,就变成了区间内某些点+a,某些点-a，也容易用tag标记进行维护。
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <bitset> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi acos(-1.0) # define eps 1e-8 # define MOD 100000000 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } const int N=100005; //Code begin... struct Seg{LL sum, tag; int p;}seg[N<<4]; struct Edge{int p, next;}edge[N<<1]; int head[N], cnt=1, node[N], pos, fdfs[N][2]; struct DFN{int id; bool flag;}dfn[N<<1]; void add_edge(int u, int v){edge[cnt].p=v; edge[cnt].next=head[u]; head[u]=cnt++;} void dfs(int x, int fa){ dfn[++pos].id=x; dfn[pos].flag=true; fdfs[x][0]=pos; for (int i=head[x]; i; i=edge[i].next) { int v=edge[i].p; if (v==fa) continue; dfs(v,x); } dfn[++pos].id=x; dfn[pos].flag=false; fdfs[x][1]=pos; } void push_up(int p){seg[p].p=seg[p<<1].p+seg[p<<1|1].p; seg[p].sum=seg[p<<1].sum+seg[p<<1|1].sum;} void push_down(int p, int L){ if (!seg[p].tag) return ; seg[p].sum+=(LL)(2*seg[p].p-L)*seg[p].tag; seg[p<<1].tag+=seg[p].tag; seg[p<<1|1].tag+=seg[p].tag; seg[p].tag=0; } void init(int p, int l, int r){ if (l<r) { int mid=(l+r)>>1; init(lch); init(rch); push_up(p); } else { seg[p].sum=dfn[l].flag?node[dfn[l].id]:-node[dfn[l].id]; seg[p].p=dfn[l].flag; } } LL query(int p, int l, int r, int R){ push_down(p,r-l+1); if (R<l) return 0; if (R>=r) return seg[p].sum; int mid=(l+r)>>1; return query(lch,R)+query(rch,R); } void update1(int p, int l, int r, int X, int val){ push_down(p,r-l+1); if (X<l||X>r) return ; if (X==l&&X==r) seg[p].sum+=val; else { int mid=(l+r)>>1; update1(lch,X,val); update1(rch,X,val); push_up(p); } } void update2(int p, int l, int r, int L, int R, int val){ push_down(p,r-l+1); if (L>r||R<l) return ; if (L<=l&&R>=r) seg[p].tag+=val, push_down(p,r-l+1); else { int mid=(l+r)>>1; update2(lch,L,R,val); update2(rch,L,R,val); push_up(p); } } int main () { int n, m, flag, u, v; scanf("%d%d",&n,&m); FOR(i,1,n) scanf("%d",node+i); FO(i,1,n) scanf("%d%d",&u,&v), add_edge(u,v), add_edge(v,u); dfs(1,0); init(1,1,n<<1); while (m--) { scanf("%d%d",&flag,&u); if (flag==3) printf("%lld\n",query(1,1,n<<1,fdfs[u][0])); else { scanf("%d",&v); if (flag==1) update1(1,1,n<<1,fdfs[u][0],v), update1(1,1,n<<1,fdfs[u][1],-v); else update2(1,1,n<<1,fdfs[u][0],fdfs[u][1],v); } } return 0; }
BZOJ 4034 树上操作(树的欧拉序列+线段树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。