[HEOI2016]树

\(\\\)

Description

给出一颗树&＃xff0c;开始只有 \(1\) 号节点有标记。

• \(\ C\ x\) 对 \(x\) 号节点打标记

• \(\ Q\ x\) 查询 \(x\) 号节点深度最深的有标记的祖先

\(\\\)

Solution

• 链剖做法&＃xff1a;

  查询直到跳到第一个有权的重链上&＃xff0c;线段树上二分即可。太板了不说了。

• DFS序&＃43;线段树做法&＃xff1a;

  一遍DFS求出DFS序&＃xff0c;子树大小以及节点深度。

  用线段树维护DFS序&＃xff0c;每个节点记录覆盖当前区间深度最深的节点编号。标记下放的时候只需选择深度更深的作为答案即可。注意设置根节点的深度&＃xff0c;否则第一次的全局标记可能会无效。

  因为DFS序中一棵子树是连续的&＃xff0c;所以标记可以看作整棵子树的区间覆盖操作。查询也很方便&＃xff0c;在递归查找时下放标记即可。

  #include
#include
#include
#include
#include
#include
#include
#define N 100010
#define gc getchar
#define Rg register
#define mid ((l&＃43;r)>>1)
using namespace std;inline int rd(){int x&＃61;0; bool f&＃61;0; char c&＃61;gc();while(!isdigit(c)){if(c&＃61;&＃61;&＃39;-&＃39;)f&＃61;1;c&＃61;gc();}while(isdigit(c)){x&＃61;(x<<1)&＃43;(x<<3)&＃43;(c^48);c&＃61;gc();}return f?-x:x;
}int n,m,tot,hd[N];int cnt,s[N],d[N],dfn[N],sz[N];struct edge{int to,nxt;}e[N];inline void add(int u,int v){e[&＃43;&＃43;tot].to&＃61;v; e[tot].nxt&＃61;hd[u]; hd[u]&＃61;tot;
}void dfs(int u,int fa){dfn[u]&＃61;&＃43;&＃43;cnt;s[cnt]&＃61;u; sz[u]&＃61;1;for(Rg int i&＃61;hd[u],v;i;i&＃61;e[i].nxt)if((v&＃61;e[i].to)!&＃61;fa){d[v]&＃61;d[u]&＃43;1;dfs(v,u);sz[u]&＃43;&＃61;sz[v];}
}struct segment{int root,ptr;inline int newnode(){return &＃43;&＃43;ptr;}struct node{int ls,rs,tag;}c[N<<1];inline void build(int &rt,int l,int r){rt&＃61;newnode();if(l&＃61;&＃61;r) return;build(c[rt].ls,l,mid);build(c[rt].rs,mid&＃43;1,r);}inline void pushdown(int rt){if(d[c[rt].tag]>d[c[c[rt].ls].tag]) c[c[rt].ls].tag&＃61;c[rt].tag;if(d[c[rt].tag]>d[c[c[rt].rs].tag]) c[c[rt].rs].tag&＃61;c[rt].tag;c[rt].tag&＃61;0;}inline void updata(int rt,int l,int r,int L,int R,int p){if(l>R||r&＃61;L&&r<&＃61;R){if(d[p]>d[c[rt].tag]) c[rt].tag&＃61;p;return;}if(c[rt].tag) pushdown(rt);if(L<&＃61;mid) updata(c[rt].ls,l,mid,L,R,p);if(R>mid) updata(c[rt].rs,mid&＃43;1,r,L,R,p);}inline int query(int rt,int l,int r,int p){if(l&＃61;&＃61;r) return c[rt].tag;if(c[rt].tag) pushdown(rt);if(p<&＃61;mid) return query(c[rt].ls,l,mid,p);else return query(c[rt].rs,mid&＃43;1,r,p);}}tree;int main(){n&＃61;rd(); m&＃61;rd();for(Rg int i&＃61;1,u,v;i}


• 并查集做法&＃xff1a;

  我们用并查集指针代表当前最近的标记节点的方向&＃xff0c;开始都指向父节点。标记一个点只需直接将指针指向自己&＃xff0c;查询即找到集合代表元素。容易发现正着处理复杂度不对&＃xff0c;因为要保证树的形态正确&＃xff0c;所以我们不能使用并查集的优化方式。

  时光倒流。开始先把所有的标记打上&＃xff0c;其余的点指向父节点。倒着模拟&＃xff0c;遇到打标记就撤销标记&＃xff0c;询问就是找到集合代表元素。可以使用路径压缩优化&＃xff0c;因为只会撤销标记&＃xff0c;任意时刻集合的代表元素必然是集合内的最优答案。

  注意一个节点可能被多次打标记&＃xff0c;在最后一次撤销标记时我们再将其与父节点 merge 在一起。

  #include
#include
#include
#include
#include
#include
#include
#include
#define N 100010
#define R register
#define gc getchar
#define mid ((l&＃43;r)>>1)
using namespace std;inline int rd(){int x&＃61;0; bool f&＃61;0; char c&＃61;gc();while(!isdigit(c)){if(c&＃61;&＃61;&＃39;-&＃39;)f&＃61;1;c&＃61;gc();}while(isdigit(c)){x&＃61;(x<<1)&＃43;(x<<3)&＃43;(c^48);c&＃61;gc();}return f?-x:x;
}int n,m,tot,hd[N],fa[N],cnt[N];struct edge{int to,nxt;}e[N<<1];inline void add(int u,int v){e[&＃43;&＃43;tot].to&＃61;v; e[tot].nxt&＃61;hd[u]; hd[u]&＃61;tot;
}void dfs(int u){for(R int i&＃61;hd[u],v;i;i&＃61;e[i].nxt)if((v&＃61;e[i].to)!&＃61;fa[u]){fa[v]&＃61;u;dfs(v);}
}struct Q{int op,x,ans;}q[N];struct UFS{int f[N];UFS(){memset(f,0,sizeof(f));}int find(int x){return x&＃61;&＃61;f[x]?x:f[x]&＃61;find(f[x]);}inline void merge(int x,int fa){f[find(x)]&＃61;find(fa);}
}ufs;int main(){n&＃61;rd(); m&＃61;rd();for(R int i&＃61;1,u,v;i}