首页 > 代码库 > bzoj1984 月下“毛景树”
bzoj1984 月下“毛景树”
Description
毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数： ? Change k w：将第k条树枝上毛毛果的个数改变为w个。 ? Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。 ? Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问： ? Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。
Input
第一行一个正整数N。 接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。 接下来是操作和询问，以“Stop”结束。
Output
对于毛毛虫的每个询问操作，输出一个答案。
Sample Input
4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop
Sample Output
9
16
【Data Range】
1<=N<=100,000，操作+询问数目不超过100,000。
保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。
16
【Data Range】
1<=N<=100,000，操作+询问数目不超过100,000。
保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。
树链剖分第二题
写完感觉不会再爱了
线段树写得我快跪了
这题是边权还要转成点权处理
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971#define N 200010using namespace std;inline LL read(){ LL 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,cnt,cnt2,tt,lca,x,y,z;struct edge{ int to,next,v,rnk;}e[2*N];struct segtree{ int l,r,mx,tag,cover;}tree[4*N];int query[N],v[N];int head[N];bool mrk[N];int depth[N],son[N],fa[N][21];int place[N],pplace[N],belong[N];char ch[100];inline void ins(int u,int v,int w,int rnk){ e[++cnt].to=v; e[cnt].v=w; e[cnt].next=head[u]; e[cnt].rnk=rnk; head[u]=cnt;}inline void insert(int u,int v,int w,int rnk){ ins(u,v,w,rnk); ins(v,u,w,rnk);}inline void dfs1(int x,int dep){ if(mrk[x])return; mrk[x]=1;depth[x]=dep;son[x]=1; for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1]; for (int i=head[x];i;i=e[i].next) if (!mrk[e[i].to]) { fa[e[i].to][0]=x; query[e[i].rnk]=e[i].to; v[e[i].to]=e[i].v; dfs1(e[i].to,dep+1); son[x]+=son[e[i].to]; }}inline void dfs2(int x,int chain){ place[x]=++tt;pplace[tt]=x; belong[x]=chain; int mx=-inf,res=-1; for (int i=head[x];i;i=e[i].next) if(e[i].to!=fa[x][0]) { if (son[e[i].to]>mx) { mx=son[e[i].to]; res=e[i].to; } } if (res==-1)return; dfs2(res,chain); for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa[x][0]&&e[i].to!=res) dfs2(e[i].to,e[i].to);}inline int LCA(int a,int b){ if (depth[a]<depth[b])swap(a,b); int res=depth[a]-depth[b]; for(int i=0;i<=20;i++) if (res & (1<<i))a=fa[a][i]; for (int i=20;i>=0;i--) if (fa[a][i]!=fa[b][i]) { a=fa[a][i]; b=fa[b][i]; } if (a==b)return a; return fa[a][0];}inline void pushdown(int k){ int l=tree[k].l,r=tree[k].r,tag=tree[k].tag,cov=tree[k].cover; tree[k].tag=0;tree[k].cover=-1; if (l==r)return; if (cov!=-1) { tree[k<<1].mx=tree[k<<1|1].mx=cov; tree[k<<1].tag=tree[k<<1|1].tag=0; tree[k<<1].cover=tree[k<<1|1].cover=cov; } if (tag) { tree[k<<1].mx+=tag; if (tree[k<<1].cover!=-1)tree[k<<1].cover+=tag; else tree[k<<1].tag+=tag; tree[k<<1|1].mx+=tag; if (tree[k<<1|1].cover!=-1)tree[k<<1|1].cover+=tag; else tree[k<<1|1].tag+=tag; } }inline void update(int k){ tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx);}inline void buildtree(int now,int l,int r){ tree[now].l=l;tree[now].r=r; tree[now].cover=-1; if (l==r) { tree[now].mx=v[pplace[l]]; return; } int mid=(l+r)>>1; buildtree(now<<1,l,mid); buildtree(now<<1|1,mid+1,r); update(now);}inline int ask_in_tree(int now,int x,int y){ pushdown(now); int l=tree[now].l,r=tree[now].r; if (l==x&&r==y)return tree[now].mx; int mid=(l+r)>>1; if (y<=mid)return ask_in_tree(now<<1,x,y); else if(x>mid)return ask_in_tree(now<<1|1,x,y); return max(ask_in_tree(now<<1,x,mid),ask_in_tree(now<<1|1,mid+1,y));}inline void change_in_tree(int now,int x,int y,int dat){ pushdown(now); int l=tree[now].l,r=tree[now].r; if (l==x&&r==y) { tree[now].mx=dat; tree[now].cover=dat; tree[now].tag=0; return; } int mid=(l+r)>>1; if (y<=mid)change_in_tree(now<<1,x,y,dat); else if (x>mid)change_in_tree(now<<1|1,x,y,dat); else { change_in_tree(now<<1,x,mid,dat); change_in_tree(now<<1|1,mid+1,y,dat); } update(now);}inline void add_in_tree(int now,int x,int y,int dat){ pushdown(now); int l=tree[now].l,r=tree[now].r; if (l==x&&r==y) { tree[now].tag+=dat; tree[now].mx+=dat; return; } int mid=(l+r)>>1; if (y<=mid)add_in_tree(now<<1,x,y,dat); else if (x>mid)add_in_tree(now<<1|1,x,y,dat); else { add_in_tree(now<<1,x,mid,dat); add_in_tree(now<<1|1,mid+1,y,dat); } update(now);}inline int ask(int from,int to){ int l,r,mx=0; while (belong[from]!=belong[to]) { l=place[belong[from]]; r=place[from]; mx=max(mx,ask_in_tree(1,l,r)); from=fa[belong[from]][0]; } l=place[to]+1;r=place[from]; if (l>r)return mx; mx=max(mx,ask_in_tree(1,l,r)); return mx;}inline void add(int from,int to,int dat){ int l,r; while (belong[from]!=belong[to]) { l=place[belong[from]]; r=place[from]; add_in_tree(1,l,r,dat); from=fa[belong[from]][0]; } l=place[to]+1;r=place[from]; if (l>r)return; add_in_tree(1,l,r,dat);}inline void change(int from,int to,int dat){ int l,r; while (belong[from]!=belong[to]) { l=place[belong[from]]; r=place[from]; change_in_tree(1,l,r,dat); from=fa[belong[from]][0]; } l=place[to]+1;r=place[from]; if (l>r)return; change_in_tree(1,l,r,dat);}int main(){ n=read(); for (int i=1;i<n;i++) { x=read(); y=read(); z=read(); insert(x,y,z,++cnt2); } dfs1(1,1); dfs2(1,1); buildtree(1,1,n); while (1) { scanf("%s",ch); if(ch[1]==‘t‘)break;//stop if (ch[1]==‘a‘)//max { x=read();y=read(); lca=LCA(x,y); printf("%d\n",max(ask(x,lca),ask(y,lca))); } if (ch[1]==‘o‘)//cover { x=read();y=read();z=read(); lca=LCA(x,y); change(x,lca,z);change(y,lca,z); } if (ch[1]==‘d‘)//add { x=read();y=read();z=read(); lca=LCA(x,y); add(x,lca,z);add(y,lca,z); } if(ch[1]==‘h‘)//change { x=read();y=read(); change_in_tree(1,place[query[x]],place[query[x]],y); } } return 0;}
bzoj1984 月下“毛景树”
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。