1984: 月下“毛景树”
Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 1314 Solved: 416
[Submit][Status][Discuss]
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个。
HINT
Source
Solution
很容易想到树链剖分，但此题权值在边上，所以思路应有所变化，即 边权下放至点
具体实现起来并不是很难。 把边权下放到较深的点，然后进行正常的链剖即可。
维护两个标记，变换和增加，变换操作的时候，同时应该把当前的增加标记置成0，而增加操作时，则无需处理变换标记。
在区间修改的时候，需要多进行一次判断；这是不同于普通点权链剖的地方。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
#define maxn 400010
int id[maxn<<],va[maxn<<],uu[maxn],vv[maxn],ww[maxn];
int n;struct data{int next,to,w;}edge[maxn<<];int head[maxn],cnt;
void add(int u,int v,int w){cnt++;edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v,int w){add(u,v,w); add(v,u,w);}
//--------------------------------------------------------------------------------------
int deep[maxn],fa[maxn],son[maxn],size[maxn],pl[maxn],sz,pr[maxn],top[maxn],pre[maxn];
void dfs_1(int now)
{
size[now]=;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=fa[now])
{
fa[edge[i].to]=now;
deep[edge[i].to]=deep[now]+;
dfs_1(edge[i].to);
if (size[son[now]]<size[edge[i].to]) son[now]=edge[i].to;
size[now]+=size[edge[i].to];
}
}
void dfs_2(int now,int chain)
{
pl[now]=++sz; pre[sz]=now; top[now]=chain;
if (son[now]) dfs_2(son[now],chain);
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=son[now] && edge[i].to!=fa[now])
dfs_2(edge[i].to,edge[i].to);
pr[now]=sz;
}
//--------------------------------------------------------------------------------------
int tree[maxn<<],delc[maxn<<],dela[maxn<<];
inline void update(int now){tree[now]=max(tree[now<<],tree[now<<|]);}
inline void pushdown(int now)
{
if (delc[now]!=-)
{
int cc=delc[now]; delc[now]=-;
delc[now<<]=cc; dela[now<<]=; tree[now<<]=cc;
delc[now<<|]=cc; dela[now<<|]=; tree[now<<|]=cc;
}
if (dela[now])
{
int aa=dela[now]; dela[now]=;
dela[now<<]+=aa; tree[now<<]+=aa;
dela[now<<|]+=aa; tree[now<<|]+=aa;
}
}
void build(int now,int l,int r)
{
delc[now]=-; dela[now]=;
if (l==r) {tree[now]=va[l];return;}
int mid=(l+r)>>;
build(now<<,l,mid); build(now<<|,mid+,r);
update(now);
}
void point_change(int now,int l,int r,int loc,int val)
{
if (l==r) {tree[now]=val;return;}
int mid=(l+r)>>;pushdown(now);
if (loc<=mid) point_change(now<<,l,mid,loc,val);
else point_change(now<<|,mid+,r,loc,val);
update(now);
}
void segment_change(int now,int l,int r,int L,int R,int val)
{
if (L<=l && R>=r) {tree[now]=val;delc[now]=val;dela[now]=;return;}
int mid=(l+r)>>;pushdown(now);
if (L<=mid) segment_change(now<<,l,mid,L,R,val);
if (R>mid) segment_change(now<<|,mid+,r,L,R,val);
update(now);
}
void segment_add(int now,int l,int r,int L,int R,int val)
{
if (L<=l && R>=r) {tree[now]+=val;dela[now]+=val;return;}
int mid=(l+r)>>;pushdown(now);
if (L<=mid) segment_add(now<<,l,mid,L,R,val);
if (R>mid) segment_add(now<<|,mid+,r,L,R,val);
update(now);
}
int segment_ask(int now,int l,int r,int L,int R)
{
if (L<=l && R>=r) return tree[now];
int mid=(l+r)>>; int ans=;pushdown(now);
if (L<=mid) ans=max(segment_ask(now<<,l,mid,L,R),ans);
if (R>mid) ans=max(ans,segment_ask(now<<|,mid+,r,L,R));
return ans;
}
//--------------------------------------------------------------------------------------
void Change(int x,int val)
{
point_change(,,n,pl[id[x]],val);
}
void Cover(int x,int y,int val)
{
while (top[x]!=top[y])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
segment_change(,,n,pl[top[x]],pl[x],val);
x=fa[top[x]];
}
if (deep[x]>deep[y]) swap(x,y);
if (x!=y) segment_change(,,n,pl[x]+,pl[y],val);//这是有别于平常的判断
}
void Add(int x,int y,int val)
{
while (top[x]!=top[y])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
segment_add(,,n,pl[top[x]],pl[x],val);
x=fa[top[x]];
}
if (deep[x]>deep[y]) swap(x,y);
if (x!=y) segment_add(,,n,pl[x]+,pl[y],val);
}
void Max(int x,int y)
{
int ans=;
while (top[x]!=top[y])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
ans=max(ans,segment_ask(,,n,pl[top[x]],pl[x]));
x=fa[top[x]];
}
if (deep[x]>deep[y]) swap(x,y);
if (x!=y) ans=max(ans,segment_ask(,,n,pl[x]+,pl[y]));
printf("%d\n",ans);
}
//--------------------------------------------------------------------------------------
int main()
{
// freopen("msn.in","r",stdin);
// freopen("msn.out","w",stdout);
n=read();
for (int i=; i<=n-; i++)
uu[i]=read(),vv[i]=read(),ww[i]=read(),insert(uu[i],vv[i],ww[i]);
dfs_1(); dfs_2(,);
for (int i=; i<=n-; i++)
if (deep[uu[i]]<deep[vv[i]]) id[i]=vv[i]; else id[i]=uu[i];
for (int i=; i<=n-; i++) va[pl[id[i]]]=ww[i];//边权下放至点，记录所下放的点的id
build(,,n);
while (true)
{
char opt[]; scanf("%s",opt);if(opt[]=='t')break;
int u=read(),v=read(),w;
switch (opt[])
{
case 'a': Max(u,v);break;
case 'o': w=read();Cover(u,v,w);break;
case 'd': w=read();Add(u,v,w);break;
case 'h': Change(u,v);break;
}
}
return ;
}
找DCrusher和Char哥帮我调过...无果，结果还得靠自己...然后发现又是二逼错误...