「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
16
「Data Range」
1<=N<=100,000，操作+询问数目不超过100,000。
保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。
题解
树链剖分水过，但是。。。尼玛是边权。。。
要把边的权搞到结点上
然后就会有一系列奇怪的问题。。
比如要记录把每一条边的权搞到了哪个结点
比如一条3到5的路径不能修改3这个点。。。诸如此类坑爹不能多说
稍微注意下线段树俩个标记的处理
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 |
#include<iostream> #include<cstdio> #include<cstring> #define N 100001 #define inf 0x7fffffff using namespace std; int n,cnt=1,sz; int head[N],deep[N],size[N],pos[N],belong[N]; int fa[N][17],id[N]; struct edge{int to,next,v;}e[N<<1]; struct seg{int l,r,mx,a,c;}t[N<<2]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt; e[++cnt].to=u;e[cnt].next=head[v];e[cnt].v=w;head[v]=cnt; } int lca(int x,int y) { if(deep[x]<deep[y])swap(x,y); int t=deep[x]-deep[y]; for(int i=0;i<=16;i++) if(t&(1<<i))x=fa[x][i]; for(int i=16;i>=0;i--) if(fa[x][i]!=fa[y][i]) {x=fa[x][i];y=fa[y][i];} if(x==y)return x; return fa[x][0]; } void pushdown(int k) { if(t[k].l==t[k].r)return; if(t[k].c!=-1) { t[k<<1].a=t[k<<1|1].a=0; t[k<<1].c=t[k<<1|1].c=t[k].c; t[k<<1].mx=t[k<<1|1].mx=t[k].c; t[k].c=-1; } if(t[k].a) { t[k<<1].mx+=t[k].a;t[k<<1|1].mx+=t[k].a; if(t[k<<1].c!=-1)t[k<<1].c+=t[k].a; else t[k<<1].a+=t[k].a; if(t[k<<1|1].c!=-1)t[k<<1|1].c+=t[k].a; else t[k<<1|1].a+=t[k].a; t[k].a=0; } } void build(int k,int l,int r) { t[k].l=l;t[k].r=r;t[k].c=-1; if(l==r)return; int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); } void pushup(int k) {t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);} void change(int k,int x,int y,int v) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&y==r){t[k].mx=t[k].c=v;return;} int mid=(l+r)>>1; if(mid>=y)change(k<<1,x,y,v); else if(mid<x)change(k<<1|1,x,y,v); else { change(k<<1,x,mid,v); change(k<<1|1,mid+1,y,v); } pushup(k); } void add(int k,int x,int y,int v) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&y==r){t[k].mx+=v;t[k].a=v;return;} int mid=(l+r)>>1; if(mid>=y)add(k<<1,x,y,v); else if(mid<x)add(k<<1|1,x,y,v); else { add(k<<1,x,mid,v); add(k<<1|1,mid+1,y,v); } pushup(k); } int ask(int k,int x,int y) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&y==r)return t[k].mx; int mid=(l+r)>>1; if(mid>=y)return ask(k<<1,x,y); else if(mid<x)return ask(k<<1|1,x,y); else return max(ask(k<<1,x,mid),ask(k<<1|1,mid+1,y)); } void solvechange(int x,int f,int v) { while(belong[x]!=belong[f]) { change(1,pos[belong[x]],pos[x],v); x=fa[belong[x]][0]; } if(pos[f]+1<=pos[x]) change(1,pos[f]+1,pos[x],v); } void solveadd(int x,int f,int v) { while(belong[x]!=belong[f]) { add(1,pos[belong[x]],pos[x],v); x=fa[belong[x]][0]; } if(pos[f]+1<=pos[x]) add(1,pos[f]+1,pos[x],v); } int solveask(int x,int f) { int mx=-inf; while(belong[x]!=belong[f]) { mx=max(mx,ask(1,pos[belong[x]],pos[x])); x=fa[belong[x]][0]; } if(pos[f]+1<=pos[x]) mx=max(mx,ask(1,pos[f]+1,pos[x])); return mx; } void solve() { char s[10]; int u,v,w,f; while(1) { scanf("%s",s); switch(s[1]) { case 't':return;break; case 'd':scanf("%d%d%d",&u,&v,&w);f=lca(u,v); solveadd(u,f,w);solveadd(v,f,w);break; case 'o':scanf("%d%d%d",&u,&v,&w);f=lca(u,v); solvechange(u,f,w);solvechange(v,f,w); break; case 'h':scanf("%d%d",&u,&w);change(1,pos[id[u]],pos[id[u]],w);break; case 'a':scanf("%d%d",&u,&v);f=lca(u,v); printf("%d\n",max(solveask(u,f),solveask(v,f))); break; } } } void dfs1(int x,int f) { size[x]=1; for(int i=1;i<=16;i++) if((1<<i)<=deep[x]) fa[x][i]=fa[fa[x][i-1]][i-1]; else break; for(int i=head[x];i;i=e[i].next) { if(e[i].to==f)continue; deep[e[i].to]=deep[x]+1; fa[e[i].to][0]=x; dfs1(e[i].to,x); size[x]+=size[e[i].to]; } } void dfs2(int x,int chain) { belong[x]=chain; pos[x]=++sz; int k=0; for(int i=head[x];i;i=e[i].next) { if(deep[x]<deep[e[i].to]) { if(size[e[i].to]>size[k])k=e[i].to; } else {id[i>>1]=x;add(1,pos[x],pos[x],e[i].v);} } if(!k)return; dfs2(k,chain); for(int i=head[x];i;i=e[i].next) if(deep[x]<deep[e[i].to]&&k!=e[i].to) dfs2(e[i].to,e[i].to); } int main() { scanf("%d",&n); for(int i=1;i<=n-1;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); insert(u,v,w); } build(1,1,n); dfs1(1,0); dfs2(1,1); solve(); return 0; } |
Subscribe
计数器 9787663
OI 课件=>
OI 课件=>