1984: 月下“毛景树”
Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 713 Solved: 245
[Submit][Status]
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
题解：
先说点儿题外话
从8点钟开始我打算写树链剖分，因为转c++以来还没有写过。
抱着不好写、写完不好调、线段树不知能不能写对的心态开始写。
写了大概1个多小时写完。
然后就交bzoj，TLE，于是我把hzwer的程序拿过来对拍，写数据生成器又写了20分钟
第一组数据就发现我的程序死循环了，我就一直debug,而我又不会用gdb，
只能输中间结果来看看哪出错了，找到出错的位置又查哪儿导致的出错，调了差不多2个小时竟然发现是dfs1写错了
卧槽！更新fa[x]我竟然写到遍历节点后去了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
改了之后交上去就A了
我以为这题线段树是重点！！！
我以为写完代码读一遍就不会犯sb错误！！！
我以为树链剖分写过好几次了不会写错！！！
我的人生就浪费在debug上了嘛。。。。。。。。。
。。。。。。
题解就不说了，就是因为把边权捆到了点上所以我不得不写LCA，造成一堆麻烦
线段树大概想一想两种运算的优先级和pushdown、pushup放对位置就可以
代码：
1.伤痕累累的代码
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#define inf 1000000000
#define maxn 100000+1000
#define maxm 500+100
#define eps 1e-10
#define ll long long
using namespace std;
struct edge{int go,next,w;}e[*maxn];
struct seg{int l,r,tag,add,mx;}t[*maxn];
int n,tot,cnt=,top[maxn],a[maxn],b[maxn],c[maxn],p[maxn],v[maxn],id[maxn];
int fa[maxn][],dep[maxn],head[maxn],son[maxn],s[maxn];
void ins(int x,int y,int z)
{
e[++tot].go=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot;
}
void insert(int x,int y,int z)
{
ins(x,y,z);ins(y,x,z);
}
void dfs(int x)
{
s[x]=;
for(int i=;i<=;i++)
if((<<i)<=dep[x])
fa[x][i]=fa[fa[x][i-]][i-];
else break;
for(int y=son[x]=,i=head[x];i;i=e[i].next)
if(dep[y=e[i].go]==)
{
dep[y]=dep[x]+;fa[y][]=x;dfs(y);
s[x]+=s[y];if(s[y]>s[son[x]])son[x]=y;
}
}
void dfs2(int x,int chain)
{
p[x]=++cnt;top[x]=chain;
if(son[x])dfs2(son[x],chain);
for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
if(y!=fa[x][]&&y!=son[x])dfs2(y,y);
}
void pushup(int k)
{
t[k].mx=max(t[k<<].mx,t[k<<|].mx);
}
void update1(int k,int x)
{
t[k].tag=x;t[k].add=;t[k].mx=x;
}
void update2(int k,int x)
{
t[k].add+=x;t[k].mx+=x;
}
void pushdown(int k)
{
if(t[k].tag!=-)
{
int x=t[k].tag;
update1(k<<,x);update1(k<<|,x);
t[k].tag=-;
}
if(t[k].add)
{
int x=t[k].add;
update2(k<<,x);update2(k<<|,x);
t[k].add=;
}
}
void build(int k,int x,int y)
{
int l=t[k].l=x,r=t[k].r=y,mid=(l+r)>>;
t[k].tag=-;t[k].add=;
if(l==r){t[k].mx=v[l];return;}
build(k<<,l,mid);build(k<<|,mid+,r);
pushup(k);
}
void cover(int k,int x,int y,int z)
{
//cout<<k<<' '<<x<<' '<<y<<' '<<z<<endl;
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&r==y){update1(k,z);return;}
pushdown(k);
if(y<=mid)cover(k<<,x,y,z);
else if(x>mid)cover(k<<|,x,y,z);
else cover(k<<,x,mid,z),cover(k<<|,mid+,y,z);
pushup(k);
}
void addd(int k,int x,int y,int z)
{
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&r==y){update2(k,z);return;}
pushdown(k);
if(y<=mid)addd(k<<,x,y,z);
else if(x>mid)addd(k<<|,x,y,z);
else addd(k<<,x,mid,z),addd(k<<|,mid+,y,z);
pushup(k);
}
int query(int k,int x,int y)
{
//cout<<k<<' '<<x<<' '<<y<<endl;
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&r==y)return t[k].mx;
pushdown(k);
if(y<=mid)return query(k<<,x,y);
else if(x>mid)return query(k<<|,x,y);
else return max(query(k<<,x,mid),query(k<<|,mid+,y));
}
int lca(int x,int y)
{
//cout<<"!!!!!!!"<<endl;
if(dep[x]<dep[y])swap(x,y);//cout<<"!!!!!!!"<<endl;
int t=dep[x]-dep[y];
for(int i=;i<=;i++)
if(t&(<<i))x=fa[x][i];//cout<<"!!!!!!!"<<endl;
if(x==y)return x;
for(int i=;i>=;i--)
if(fa[x][i]!=fa[y][i])
{x=fa[x][i];y=fa[y][i];}; //cout<<"!!!!!!!"<<endl;
return fa[x][];
}
void solveadd(int x,int f,int z)
{
while(top[x]!=top[f])
{
addd(,p[top[x]],p[x],z);
x=fa[top[x]][];
}
if(f!=x)addd(,p[f]+,p[x],z);
}
void solvecover(int x,int f,int z)
{
while(top[x]!=top[f])
{
cover(,p[top[x]],p[x],z);
x=fa[top[x]][];
//cout<<"!!!!!"<<endl;
}
// cout<<"!!!!!!"<<endl;
// cout<<f<<' '<<x<<' '<<p[f]<<' '<<p[x]<<endl;
if(f!=x)cover(,p[f]+,p[x],z);
}
int solveask(int x,int f)
{
int ans=;
while(top[x]!=top[f])
{
//cout<<x<<' '<<top[x]<<' '<<p[x]<<' '<<p[top[x]]<<endl;
ans=max(ans,query(,p[top[x]],p[x]));
x=fa[top[x]][];
}
if(f!=x)ans=max(ans,query(,p[f]+,p[x]));
return ans;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
insert(a[i],b[i],c[i]);
}
dep[]=;
dfs();
// for(int i=1;i<=n;i++)cout<<i<<' '<<dep[i]<<endl;
dfs2(,);
for(int i=;i<=n;i++)
// for(int j=0;j<=16;j++)cout<<i<<' '<<j<<' '<<fa[i][j]<<endl;
// for(int i=0;i<=n;i++)cout<<i<<' '<<top[i]<<' '<<p[i]<<' '<<son[i]<<endl;
v[]=;
for(int i=;i<n;i++)id[i]=(dep[a[i]]>dep[b[i]])?a[i]:b[i];
for(int i=;i<n;i++)v[p[id[i]]]=c[i];
//for(int i=1;i<=n;i++)cout<<i<<' '<<v[i]<<' '<<id[i]<<' '<<p[i]<<endl; build(,,n);
//for(int k=1;k<=4*n;k++)cout<<t[k].l<<' '<<t[k].r<<' '<<t[k].tag<<' '<<t[k].add<<' '<<t[k].mx<<endl;
char s[];
int x,y,z,f;
while()
{
//cout<<"!!!!!!!"<<endl;
//for(int k=1;k<=4*n;k++)cout<<t[k].l<<' '<<t[k].r<<' '<<t[k].tag<<' '<<t[k].add<<' '<<t[k].mx<<endl;
scanf("%s",s);//cout<<s<<endl;
switch(s[])
{
case 't':return ;break;
case 'd':scanf("%d%d%d",&x,&y,&z);f=lca(x,y);
solveadd(x,f,z);solveadd(y,f,z);break;
case 'o':scanf("%d%d%d",&x,&y,&z);f=lca(x,y);
solvecover(x,f,z);solvecover(y,f,z);
break;
case 'h':scanf("%d%d",&x,&z);cover(,p[id[x]],p[id[x]],z);break;
case 'a':scanf("%d%d",&x,&y);f=lca(x,y);
printf("%d\n",max(solveask(x,f),solveask(y,f)));
//cout<<solveask(x,f)<<' '<<solveask(y,f)<<endl;
break;
}
}
}
2.去掉调试
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#define inf 1000000000
#define maxn 100000+1000
#define maxm 500+100
#define eps 1e-10
#define ll long long
using namespace std;
struct edge{int go,next,w;}e[*maxn];
struct seg{int l,r,tag,add,mx;}t[*maxn];
int n,tot,cnt=,top[maxn],a[maxn],b[maxn],c[maxn],p[maxn],v[maxn],id[maxn];
int fa[maxn][],dep[maxn],head[maxn],son[maxn],s[maxn];
void ins(int x,int y,int z)
{
e[++tot].go=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot;
}
void insert(int x,int y,int z)
{
ins(x,y,z);ins(y,x,z);
}
void dfs(int x)
{
s[x]=;
for(int i=;i<=;i++)
if((<<i)<=dep[x])
fa[x][i]=fa[fa[x][i-]][i-];
else break;
for(int y=son[x]=,i=head[x];i;i=e[i].next)
if(dep[y=e[i].go]==)
{
dep[y]=dep[x]+;fa[y][]=x;dfs(y);
s[x]+=s[y];if(s[y]>s[son[x]])son[x]=y;
}
}
void dfs2(int x,int chain)
{
p[x]=++cnt;top[x]=chain;
if(son[x])dfs2(son[x],chain);
for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
if(y!=fa[x][]&&y!=son[x])dfs2(y,y);
}
void pushup(int k)
{
t[k].mx=max(t[k<<].mx,t[k<<|].mx);
}
void update1(int k,int x)
{
t[k].tag=x;t[k].add=;t[k].mx=x;
}
void update2(int k,int x)
{
t[k].add+=x;t[k].mx+=x;
}
void pushdown(int k)
{
if(t[k].tag!=-)
{
int x=t[k].tag;
update1(k<<,x);update1(k<<|,x);
t[k].tag=-;
}
if(t[k].add)
{
int x=t[k].add;
update2(k<<,x);update2(k<<|,x);
t[k].add=;
}
}
void build(int k,int x,int y)
{
int l=t[k].l=x,r=t[k].r=y,mid=(l+r)>>;
t[k].tag=-;t[k].add=;
if(l==r){t[k].mx=v[l];return;}
build(k<<,l,mid);build(k<<|,mid+,r);
pushup(k);
}
void cover(int k,int x,int y,int z)
{
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&r==y){update1(k,z);return;}
pushdown(k);
if(y<=mid)cover(k<<,x,y,z);
else if(x>mid)cover(k<<|,x,y,z);
else cover(k<<,x,mid,z),cover(k<<|,mid+,y,z);
pushup(k);
}
void addd(int k,int x,int y,int z)
{
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&r==y){update2(k,z);return;}
pushdown(k);
if(y<=mid)addd(k<<,x,y,z);
else if(x>mid)addd(k<<|,x,y,z);
else addd(k<<,x,mid,z),addd(k<<|,mid+,y,z);
pushup(k);
}
int query(int k,int x,int y)
{
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&r==y)return t[k].mx;
pushdown(k);
if(y<=mid)return query(k<<,x,y);
else if(x>mid)return query(k<<|,x,y);
else return max(query(k<<,x,mid),query(k<<|,mid+,y));
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
int t=dep[x]-dep[y];
for(int i=;i<=;i++)
if(t&(<<i))x=fa[x][i];
if(x==y)return x;
for(int i=;i>=;i--)
if(fa[x][i]!=fa[y][i])
{x=fa[x][i];y=fa[y][i];};
return fa[x][];
}
void solveadd(int x,int f,int z)
{
while(top[x]!=top[f])
{
addd(,p[top[x]],p[x],z);
x=fa[top[x]][];
}
if(f!=x)addd(,p[f]+,p[x],z);
}
void solvecover(int x,int f,int z)
{
while(top[x]!=top[f])
{
cover(,p[top[x]],p[x],z);
x=fa[top[x]][];
}
if(f!=x)cover(,p[f]+,p[x],z);
}
int solveask(int x,int f)
{
int ans=;
while(top[x]!=top[f])
{
ans=max(ans,query(,p[top[x]],p[x]));
x=fa[top[x]][];
}
if(f!=x)ans=max(ans,query(,p[f]+,p[x]));
return ans;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
insert(a[i],b[i],c[i]);
}
dep[]=;
dfs();
dfs2(,);
for(int i=;i<=n;i++)
v[]=;
for(int i=;i<n;i++)id[i]=(dep[a[i]]>dep[b[i]])?a[i]:b[i];
for(int i=;i<n;i++)v[p[id[i]]]=c[i];
build(,,n);
char s[];
int x,y,z,f;
while()
{
scanf("%s",s);
switch(s[])
{
case 't':return ;break;
case 'd':scanf("%d%d%d",&x,&y,&z);f=lca(x,y);
solveadd(x,f,z);solveadd(y,f,z);break;
case 'o':scanf("%d%d%d",&x,&y,&z);f=lca(x,y);
solvecover(x,f,z);solvecover(y,f,z);
break;
case 'h':scanf("%d%d",&x,&z);cover(,p[id[x]],p[id[x]],z);break;
case 'a':scanf("%d%d",&x,&y);f=lca(x,y);
printf("%d\n",max(solveask(x,f),solveask(y,f)));
break;
}
}
}
3.不求LCA也过了，哈哈。不过竟然只快了不到1秒钟QAQ
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#define inf 1000000000
#define maxn 100000+1000
#define maxm 500+100
#define eps 1e-10
#define ll long long
using namespace std;
struct edge{int go,next,w;}e[*maxn];
struct seg{int l,r,tag,add,mx;}t[*maxn];
int n,tot,cnt=,top[maxn],a[maxn],b[maxn],c[maxn],p[maxn],v[maxn],id[maxn];
int fa[maxn],dep[maxn],head[maxn],son[maxn],s[maxn];
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;
}
void ins(int x,int y,int z)
{
e[++tot].go=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot;
}
void insert(int x,int y,int z)
{
ins(x,y,z);ins(y,x,z);
}
void dfs(int x)
{
s[x]=;
for(int y=son[x]=,i=head[x];i;i=e[i].next)
if(dep[y=e[i].go]==)
{
dep[y]=dep[x]+;fa[y]=x;dfs(y);
s[x]+=s[y];if(s[y]>s[son[x]])son[x]=y;
}
}
void dfs2(int x,int chain)
{
p[x]=++cnt;top[x]=chain;
if(son[x])dfs2(son[x],chain);
for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
if(y!=fa[x]&&y!=son[x])dfs2(y,y);
}
void pushup(int k)
{
t[k].mx=max(t[k<<].mx,t[k<<|].mx);
}
void update1(int k,int x)
{
t[k].tag=x;t[k].add=;t[k].mx=x;
}
void update2(int k,int x)
{
t[k].add+=x;t[k].mx+=x;
}
void pushdown(int k)
{
if(t[k].tag!=-)
{
int x=t[k].tag;
update1(k<<,x);update1(k<<|,x);
t[k].tag=-;
}
if(t[k].add)
{
int x=t[k].add;
update2(k<<,x);update2(k<<|,x);
t[k].add=;
}
}
void build(int k,int x,int y)
{
int l=t[k].l=x,r=t[k].r=y,mid=(l+r)>>;
t[k].tag=-;t[k].add=;
if(l==r){t[k].mx=v[l];return;}
build(k<<,l,mid);build(k<<|,mid+,r);
pushup(k);
}
void cover(int k,int x,int y,int z)
{
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&r==y){update1(k,z);return;}
pushdown(k);
if(y<=mid)cover(k<<,x,y,z);
else if(x>mid)cover(k<<|,x,y,z);
else cover(k<<,x,mid,z),cover(k<<|,mid+,y,z);
pushup(k);
}
void addd(int k,int x,int y,int z)
{
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&r==y){update2(k,z);return;}
pushdown(k);
if(y<=mid)addd(k<<,x,y,z);
else if(x>mid)addd(k<<|,x,y,z);
else addd(k<<,x,mid,z),addd(k<<|,mid+,y,z);
pushup(k);
}
int query(int k,int x,int y)
{
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&r==y)return t[k].mx;
pushdown(k);
if(y<=mid)return query(k<<,x,y);
else if(x>mid)return query(k<<|,x,y);
else return max(query(k<<,x,mid),query(k<<|,mid+,y));
}
void solveadd(int x,int y,int z)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
addd(,p[top[x]],p[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(x!=y)addd(,p[x]+,p[y],z);
}
void solvecover(int x,int y,int z)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
cover(,p[top[x]],p[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(x!=y)cover(,p[x]+,p[y],z);
}
int solveask(int x,int y)
{
int ans=;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=max(ans,query(,p[top[x]],p[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(x!=y)ans=max(ans,query(,p[x]+,p[y]));
return ans;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();
for(int i=;i<n;i++)
{
a[i]=read();b[i]=read();c[i]=read();
insert(a[i],b[i],c[i]);
}
dep[]=;
dfs();
dfs2(,);
for(int i=;i<=n;i++)
v[]=;
for(int i=;i<n;i++)id[i]=(dep[a[i]]>dep[b[i]])?a[i]:b[i];
for(int i=;i<n;i++)v[p[id[i]]]=c[i];
build(,,n);
char s[];
int x,y,z,f;
while()
{
scanf("%s",s);
switch(s[])
{
case 't':return ;break;
case 'd':x=read();y=read();z=read();
solveadd(x,y,z);break;
case 'o':x=read();y=read();z=read();
solvecover(x,y,z);
break;
case 'h':x=read();z=read();cover(,p[id[x]],p[id[x]],z);break;
case 'a':x=read();y=read();
printf("%d\n",solveask(x,y));
break;
}
}
}