C语言网站开发pdf,物联网设计,岳阳seo优化,北沙滩网站建设来自FallDream的博客#xff0c;未经允许#xff0c;请勿转载#xff0c;谢谢。 Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器#xff0c;你可以通过一行命令安装某一个软件包#xff0c;然后软件包管理器会帮助你从软件源下载软件包#xff0c;同时…来自FallDream的博客未经允许请勿转载谢谢。 Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器你可以通过一行命令安装某一个软件包然后软件包管理器会帮助你从软件源下载软件包同时自动解决所有的依赖即下载安装这个软件包的安装所依赖的其它软件包完成所有的配置。Debian/Ubuntu使用的apt-getFedora/CentOS使用的yum以及OSX下可用的homebrew都是优秀的软件包管理器。 你决定设计你自己的软件包管理器。不可避免地你要解决软件包之间的依赖问题。如果软件包A依赖软件包B那么安装软件包A以前必须先安装软件包B。同时如果想要卸载软件包B则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且由于你之前的工作除0号软件包以外在你的管理器当中的软件包都会依赖一个且仅一个软件包而0号软件包不依赖任何一个软件包。依赖关系不存在环若有m(m≥2)个软件包A1,A2,A3,…,Am其中A1依赖A2A2依赖A3A3依赖A4……Am−1依赖Am而Am依赖A1则称这m个软件包的依赖关系构成环当然也不会有一个软件包依赖自己。 现在你要为你的软件包管理器写一个依赖解决程序。根据反馈用户希望在安装和卸载某个软件包时快速地知道这个操作实际上会改变多少个软件包的安装状态即安装操作会安装多少个未安装的软件包或卸载操作会卸载多少个已安装的软件包你的任务就是实现这个部分。注意安装一个已安装的软件包或卸载一个未安装的软件包都不会改变任何软件包的安装状态即在此情况下改变安装状态的软件包数为0。 把安装看成1未安装看成0 发现安装操作就是查询它到根上0的数量 并把他们都变成1 卸载操作就是查询子树内1的数量并把他们都变成0 所以树剖之后线段树就行了 #includeiostream
#includecstdio
#define MN 100000
using namespace std;
inline int read()
{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;
}int n,head[MN5],cnt0,q,size[MN5],mx[MN5],dep[MN5],nl[MN5],nr[MN5],dn0,top[MN5],fa[MN5];
struct edge{int to,next;}e[MN5];
inline void ins(int f,int t){e[cnt](edge){t,head[f]};head[f]cnt;}
struct Tree{int l,r,x,val,tag;}T[MN*45];void Pre(int x)
{size[x]1;mx[x]0;for(int ihead[x];i;ie[i].next){dep[e[i].to]dep[x]1;Pre(e[i].to);size[x]size[e[i].to];if(size[e[i].to]size[mx[x]]) mx[x]e[i].to;}
}void Dfs(int x,int tp)
{top[x]tp;nl[x]dn;if(mx[x]) Dfs(mx[x],tp);for(int ihead[x];i;ie[i].next)if(e[i].to!mx[x]) Dfs(e[i].to,e[i].to);nr[x]dn;
} void Build(int x,int l,int r)
{if((T[x].ll)(T[x].rr)) return;int midlr1;Build(x1,l,mid);Build(x1|1,mid1,r);
}inline void mark(int x,int v)
{T[x].tag1;T[x].valv;T[x].x(T[x].r-T[x].l1)*v;
}void pushdown(int x)
{T[x].tag0;mark(x1,T[x].val);mark(x1|1,T[x].val);
}int Query(int x,int l,int r,int ad)
{if(T[x].llT[x].rr){int ansT[x].x;mark(x,ad);return ans;}if(T[x].tag) pushdown(x);int midT[x].lT[x].r1,ans0;if(rmid) ansQuery(x1,l,r,ad);else if(lmid) ansQuery(x1|1,l,r,ad);else ansQuery(x1,l,mid,ad)Query(x1|1,mid1,r,ad); return T[x].xT[x1].xT[x1|1].x,ans;
}int Solve_Chain(int x)
{int sum0;for(;x;xfa[top[x]])sumdep[x]-dep[top[x]]1-Query(1,nl[top[x]],nl[x],1);return sum;
}int Solve_Tree(int x){return Query(1,nl[x],nr[x],0);}
char op[20];
int main()
{nread();for(int i2;in;i) fa[i]read()1,ins(fa[i],i);Pre(1);Dfs(1,1);Build(1,1,n);qread(); for(int i1;iq;i){scanf(%s,op1);int xread()1;if(op[1]i) printf(%d\n,Solve_Chain(x));if(op[1]u) printf(%d\n,Solve_Tree (x));}return 0;
} 转载于:https://www.cnblogs.com/FallDream/p/Noi2015d1t2.html
