网站seo描述,行业门户网站运营方案,怎么做网站链接的快捷方式,wordpress 推送到微信清明梦超能力者黄YY
题目连接
https://www.nowcoder.com/acm/contest/206/I
暂时有两种做法.
算法一
涉及:树链剖分,扫描线
在一个线段的情况下,我们可以把一个染色区间拆成左端点处增加事件,右端点处删除事件. 维护一颗权值线段树. 这样,端点从小到大扫描时,遇到增加事件…清明梦超能力者黄YY
题目连接
https://www.nowcoder.com/acm/contest/206/I
暂时有两种做法.
算法一
涉及:树链剖分,扫描线
在一个线段的情况下,我们可以把一个染色区间拆成左端点处增加事件,右端点处删除事件. 维护一颗权值线段树. 这样,端点从小到大扫描时,遇到增加事件就在线段树指定位置1,遇到删除事件就在线段树指定位置-1.
那么要回答一个点的答案只需要扫到这个点的时候,在权值线段树里二分kkk大值即可.
这个搬到了树上,我们照样可以使用扫描线的方法来做.
对于每一个染色区间,将其剖到树链上去,可以剖出最多log(n)log(n)log(n)个小区间.
这些小区间的深度较小的端点加入增加事件,深度较大的端点加入删除事件.
然后对整棵树按照dfndfndfn序列从小到大依次扫描即可,注意扫描的过程中也要维护一颗权值线段树.
算法二
涉及:dfs,权值线段树合并
对于每个询问u,vu,vu,v,应该在uuu处加入增加事件,在vvv处加入增加事件,在lca(u,v)lca(u,v)lca(u,v)处加入删除事件,在faz[lca(u,v)]faz[lca(u,v)]faz[lca(u,v)]处加入删除事件.因此每个询问会产生444个事件.
我们采用dfs的顺序,每个点维护一颗权值线段树,然后后序遍历到达一个节点时候,先将它所有儿子的线段树进行合并,合并完成后,将该点涉及到的增加或删除事件执行到线段树上,此时,该点的权值线段树维护的就是横跨这个节点的所有染色区间.
然后在权值线段树上进行kkk大询问即可得到该点的答案.
算法一.代码
#include iostream
#include algorithm
#include cstring
#include vector
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)
#define clr(x) memset(x,0,sizeof(x))const int N 100007;struct edge{int v,nxt;
}es[N1];int head[N],tot;void addedge(int u,int v){es[tot].v v;es[tot].nxt head[u];head[u] tot;
}int faz[N],siz[N],dep[N],top[N],son[N],dfn[N],rnk[N],idx;void dfs1(int u,int fa,int deep) {faz[u] fa;siz[u] 1;dep[u] deep;for(int e head[u];e ! -1;e es[e].nxt) {int v es[e].v;if(v fa) continue;dfs1(v,u,deep1);siz[u] siz[v];if(!son[u] || siz[v] siz[son[u]])son[u] v;}
}void dfs2(int u,int tp) {dfn[u] idx;rnk[idx] u;top[u] tp;if(son[u]) dfs2(son[u],tp);for(int e head[u];e ! -1;e es[e].nxt) {int v es[e].v;if(son[u] ! v faz[u] ! v)dfs2(v,v);}
}struct node{int val,len;node(int val 0,int len 1):val(val),len(len){}
}ns[N2];node maintain(node lch,node rch) {return node(lch.val rch.val,lch.len rch.len);
}void change(int o,int l,int r,int pos,int val) {if(l r) {ns[o].val val;return ;}int mid (l r) 1;if(pos mid)change(o1,l,mid,pos,val);elsechange(o1|1,mid1,r,pos,val);ns[o] maintain(ns[o1],ns[o1|1]);
}int kth(int o,int l,int r,int x) {if(ns[o].val x) return 0;if(l r) return l; int mid (l r) 1;if(x ns[o1].val)return kth(o1|1,mid1,r,x-ns[o1].val);elsereturn kth(o1,l,mid,x);
}struct event{int tp,val;event(int tp 0,int val 0):tp(tp),val(val){}
};std::vectorevent events[N];int color[N];void modify(int x,int y,int id) {while(top[x] ! top[y]) {if(dep[top[x]] dep[top[y]])std::swap(x,y);events[dfn[x]].push_back(event(-1,id));events[dfn[top[x]]].push_back(event(1,id));x faz[top[x]];}if(dep[x] dep[y])std::swap(x,y);events[dfn[x]].push_back(event(-1,id));events[dfn[y]].push_back(event(1,id));
}int n,m,k;
int ans[N];
int main() {memset(head,-1,sizeof(head));std::ios::sync_with_stdio(false);std::cin n m k;rep(i,1,n-1) {int x,y;std::cin x y;addedge(x,y);addedge(y,x);}dfs1(1,-1,0);dfs2(1,1);rep(i,1,m){int u,v,c;std::cin u v c;color[m1-i] c;modify(u,v,m1-i);}rep(i,1,n) {for(auto e : events[i]){if(e.tp 1)change(1,1,n,e.val,1);}ans[rnk[i]] color[kth(1,1,n,k)];for(auto e : events[i]) {if(e.tp -1)change(1,1,n,e.val,-1);}}rep(i,1,n) {std::cout ans[i] ;}return 0;
}算法二.代码
#include iostream
#include algorithm
#include cstring
#include vector
#include assert.h
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)
#define clr(x) memset(x,0,sizeof(x))
#define setinf(x) memset(x,0x3f,sizeof(x))const int N 100007;
std::vectorint edge[N];struct node {int sum,lch,rch;node(int sum 0,int lch 0,int rch 0):sum(sum),lch(lch),rch(rch){}
}ns[N*60];
int tot;node maintain(node lch,node rch,int l,int r) {return node(lch.sumrch.sum,l,r);
}void insert(int o,int l,int r,int pos,int add) {if(!o)o tot;if(l r) {ns[o].sum add;return ;}int mid (l r) 1;if(pos mid)insert(ns[o].lch,l,mid,pos,add);elseinsert(ns[o].rch,mid1,r,pos,add);ns[o] maintain(ns[ns[o].lch],ns[ns[o].rch],ns[o].lch,ns[o].rch);
}node query(int o,int l,int r,int ql,int qr) {if(o 0) return ns[0];if(ql l r qr)return ns[o];if(r ql || qr l)return ns[0];int mid (l r) 1;node lch query(ns[o].lch,l,mid,ql,qr);node rch query(ns[o].rch,mid1,r,ql,qr);return maintain(lch,rch,0,0);
}int merge(int a,int b) {if(!a) return b;if(!b) return a;int o tot;assert(o N*60);ns[o].sum ns[a].sum ns[b].sum;ns[o].lch merge(ns[a].lch,ns[b].lch);ns[o].rch merge(ns[a].rch,ns[b].rch);return o;
}int ans[N],color[N];int faz[N],siz[N],top[N],dep[N],dfn[N],son[N],idx;void dfs1(int u,int fa,int deep) {faz[u] fa;dep[u] deep;siz[u] 1;for(auto v : edge[u]) {if(v fa) continue;dfs1(v,u,deep1);siz[u] siz[v];if(siz[son[u]] siz[v])son[u] v;}
}void dfs2(int u,int tp) {dfn[u] idx;top[u] tp;if(son[u])dfs2(son[u],tp);for(auto v : edge[u]) {if(v faz[u] || v son[u]) continue;dfs2(v,v);}
}int lca(int u,int v) {while(top[u] ! top[v]) {if(dep[top[u]] dep[top[v]])v faz[top[v]];elseu faz[top[u]];}return dep[u] dep[v] ? v : u;
}int kth(int o,int l,int r,int k) {if(!o || ns[o].sum k)return 0;if(l r) return l;int mid (l r) 1;if(k ns[ns[o].lch].sum)return kth(ns[o].lch,l,mid,k);elsereturn kth(ns[o].rch,mid1,r,k-ns[ns[o].lch].sum);
}int n,m,k;
int root[N];
std::vectorint add[N],dec[N];
void dfs(int u,int fa) {for(auto v : edge[u]) {if(v fa) continue;dfs(v,u);root[u] merge(root[u],root[v]);}for(auto x : dec[u]){insert(root[u],1,n,x,-1);}for(auto y : add[u]){insert(root[u],1,n,y,1);}ans[u] color[kth(root[u],1,n,k)];
}int main() {std::ios::sync_with_stdio(false);std::cin n m k;rep(i,1,n-1) {int u,v;std::cin u v;edge[u].push_back(v);edge[v].push_back(u);}dfs1(1,0,0);dfs2(1,1);for(int i m;i 1;--i) {int u,v;std::cin u v color[i];add[u].push_back(i);add[v].push_back(i);int _lca lca(u,v);dec[_lca].push_back(i);dec[faz[_lca]].push_back(i);}dfs(1,0);rep(i,1,n) {std::cout ans[i] ;}std::cout std::endl;return 0;
}
