BZOJ1984: 月下“毛景树”

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

Sample Output

9
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;

         }

     }

 }

巴特西