USACO10FEB]慢下来Slowing down dfs序线段树

分手后的思念是犯贱 2021-12-10 13:04 147阅读 0赞

# \[USACO10FEB\]慢下来Slowing down #

[题面 洛谷P2982][_P2982]

本来想写树剖来着

暴力数据结构直接模拟，每头牛回到自己的农场后，其子树下的所有牛回到农舍时，必定会经过此牛舍，即：每头牛回舍后，会对其子树所有点造成多一次慢下来的机会。所以先使用\\(dfs\\)序将子树操作转化为线性区间操作，之后使用线段树区间修改当前子树全部加一，单点查询当前点覆盖次数。

注意：

*  在\\(dfs\\)序上，节点\\(x\\)的子树为区间\\(\\text\{\[dfn\[x\], dfn\[x\]+sz\[x\]-1\]\}\\)，其中子树大小\\(\\text\{sz\[x\]\}\\)包含\\(x\\)本身

*AC Code:*

#include <cstdio> #define MAXN 100010 #define sl ((x)<<1) #define sr ((x)<<1|1) using namespace std; int n; int head[MAXN],nxt[MAXN*2],vv[MAXN*2],tot; inline void add_edge(int u, int v){ vv[++tot]=v; nxt[tot]=head[u]; head[u]=tot; } int dfn[MAXN],cnt,sz[MAXN]; void dfs(int u){ dfn[u]=++cnt; sz[u]=1; for(register int i=head[u];i;i=nxt[i]){ int v=vv[i]; if(dfn[v]!=0) continue; dfs(v); sz[u]+=sz[v]; } } struct nod{ int l, r, val, lazy; } tre[MAXN*4]; void built(int x, int l, int r){ tre[x].l=l,tre[x].r=r; if(l==r) return; int mid=(l+r)>>1; built(sl, l, mid); built(sr, mid+1, r); } void push_down(int x){ if(tre[x].lazy==0) return; tre[sl].lazy+=tre[x].lazy; tre[sr].lazy+=tre[x].lazy; tre[sl].val+=tre[x].lazy*(tre[sl].r-tre[sl].l+1); tre[sr].val+=tre[x].lazy*(tre[sr].r-tre[sr].l+1); tre[x].lazy=0; } void change(int x, int l, int r, int val){ if(l<=tre[x].l&&tre[x].r<=r){ tre[x].val+=val*(tre[x].r-tre[x].l+1); tre[x].lazy+=val; return; } push_down(x); int mid=(tre[x].l+tre[x].r)>>1; if(l<=mid) change(sl, l, r, val); if(r>mid) change(sr, l, r, val); tre[x].val=tre[sl].val+tre[sr].val; } int query(int x, int q){ if(tre[x].l==tre[x].r) return tre[x].val; push_down(x); int mid=(tre[x].l+tre[x].r)>>1; if(q<=mid) return query(sl, q); else return query(sr, q); } int main() { scanf("%d", &n); for(int i=1;i<=n-1;++i){ int a,b;scanf("%d %d", &a, &b); add_edge(a,b); add_edge(b,a); } dfs(1); built(1,1,n); for(int i=1;i<=n;++i){ int q;scanf("%d", &q); printf("%d\n", query(1, dfn[q])); change(1, dfn[q], dfn[q]+sz[q]-1, 1); } return 0; }

转载于:https://www.cnblogs.com/santiego/p/10987232.html

[_P2982]: https://www.luogu.org/problemnew/show/P2982