大佬教程收集整理的这篇文章主要介绍了SPOJ 2798 QTREE3 - Query on a tree again!,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
Time limit 2000 ms
@H_117_18@memory limit 1572864 kBCode length Limit 50000 B
OS Linux
Language limit All except: ERL JS-RHINO NODEJS PERL6 VB.NET //c++呢?Java呢?Python呢?明明可以的
source VNOI Marathon ‘08 - Round 6/DivA Problem Setter: Blue Mary
Author Fudan University Problem Setters
两年后写的第二篇树剖,还是找了一两天的bug,最后发现,dfs1()
里,if(v==t[u].fa) conTinue;
被我写成了if(v==t[u].fa) return;
。这样例里的树好像也不水了……而且我记得之前把建好的树输出,也没发现树上少了哪个点来着……不知道这个错误发生之前是不是有其他什么bug……
[HAOI2015]树上操作 这篇的操作3也是从根节点到给定点这一路的修改,我当年还觉得那时自己想的优化(因为一个点已经固定为根节点1,所以跳链时不用比较两条链顶端的深度,只需要下面那个点不停向上到达根就好)挺不错来着,结果现在发现只是那常规操作……
板子没有解题思路
#include<cstdio> #include<cString> #include<algorithm> int T; int n,q; //对于每个黑色点,线段树上的值对应点的新id //对于每个白色点,线段树上的值为inf struct Edge{ int nxt,to; }e[200010]; int cnt=1,head[100010]; void add(int u,int v) { e[cnt]={head[u],v}; head[u]=cnt++; e[cnt]={head[v],u}; head[v]=cnt++; } struct Tree{ int fa,dep,sz,wson; int id,top; }t[100010]; void dfs1(int u,int fa) { t[u].fa=fa; t[u].dep=t[fa].dep+1; t[u].sz=1; int maxn=-1; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(v==fa) conTinue;//就是这里,之前写成return了 dfs1(v,u); int temp=t[v].sz; t[u].sz+=temp; if(temp>maxn) { maxn=temp; t[u].wson=v; } } } int id=1; int mp[100010];//用新的id查询老的id void dfs2(int u,int top) { t[u].top=top; mp[id]=u; t[u].id=id++; if(t[u].sz==1) return; dfs2(t[u].wson,top); for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(v==t[u].wson||v==t[u].fa) conTinue; dfs2(v,v); } } const int inf=0x7f7f7f7f; struct Segtree{ int l,r;//有点想改变码风,把这两个放到参数里去,以便和主席树统一 int mn; }s[400010]; void build(int x,int l,int r) { s[x]={l,r,inf}; if(l==r) return; int mid=l+r>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); } void update(int x,int pos) { if(s[x].l==s[x].r&&s[x].l==pos) { if(s[x].mn==inf)//染成黑色 s[x].mn=pos;//赋值成新的id else//染成白色 s[x].mn=inf; return; } int mid=s[x].l+s[x].r>>1; if(pos<=mid) update(x<<1,pos); else update(x<<1|1,pos); s[x].mn=std::min(s[x<<1].mn,s[x<<1|1].mn); } int que(int x,int r)//返回所求点新id { if(l<=s[x].l&&s[x].r<=r) return s[x].mn; int mid=s[x].l+s[x].r>>1; int ans=inf; if(l<=mid) ans=std::min(ans,que(x<<1,r)); if(r>mid) ans=std::min(ans,que(x<<1|1,r)); return ans; } void opt0(int u)//改变u号点颜色 { update(1,t[u].id); } int opt1(int u)//返回1到u的第一个黑点的老id { int ans=inf; while(u) { ans=std::min(ans,que(1,t[t[u].top].id,t[u].id)); u=t[t[u].top].fa; } if(ans==inf) ans=-1; else ans=mp[ans]; return ans; } int main() { //freopen("test.in","r",stdin); scanf("%d%d",&n,&q); for(int i=1,u,v;i<n;i++) { scanf("%d%d",&u,&v); add(u,v); } dfs1(1,0); dfs2(1,1); build(1,1,n); while(q--) { int opt,u; scanf("%d%d",&opt,&u); if(opt) printf("%d\n",opt1(u)); else opt0(u); } return 0; }
以上是大佬教程为你收集整理的SPOJ 2798 QTREE3 - Query on a tree again!全部内容,希望文章能够帮你解决SPOJ 2798 QTREE3 - Query on a tree again!所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。