题目大意：
　　给定一个环长为奇数的带权基环树，支持以下两种操作：
　　　　1.两点间最短路取反；
　　　　2.两点间最短路求最大子段和。
思路：
　　首先找出环，然后对每一个外向树轻重链剖分，
　　用线段树维护每一个区间的和、前缀和最值、后缀和最值及子段最值。
　　每次修改时，分下列两种情况讨论：
　　　　1.两个点在同一棵外向树上，按照普通的树链剖分修改，线段树上打取反的标记。
　　　　2.两个点再不同外向树上，先各自沿着链往上跳，然后都跳到环上的时候，可以将两个点在环中的序号减一减，对环长取模，看看哪个小。
　　查询时大致和修改一样，但是合并两个区间的时候很麻烦，要注意考虑完全。
细节：
　　1.找环可以在DFS的时候和树剖一起完成，也可以用并查集写，两个效率差不多。
　　2.标记可以打好几次，所以不能简单地把标记赋值为true，而是每次取反。
这题代码量比较大，vjudge上除了周骏东都是10K左右。网上的题解也很少，中英文都没有找到。
一开始写挂的地方特别多，对拍对了好多次才排出所有的错。

 #include<cstdio>

 #include<cctype>

 #include<vector>

 inline int getint() {

     char ch;

     bool neg=false;

     while(!isdigit(ch=getchar())) if(ch=='-') neg=true;

     int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return neg?-x:x;

 }

 const int V=;

 struct Edge {

     int to,w;

 };

 std::vector<Edge> e[V];

 inline void add_edge(const int u,const int v,const int w) {

     e[u].push_back((Edge){v,w});

 }

 int par[V],size[V],son[V],cyc[V],id[V],w[V],root[V],dep[V],top[V];

 int cnt_cyc,cnt;

 bool on_cycle[V];

 bool dfs1(const int x,const int p) {

     if(par[x]||(x==&&p!=)) {

         on_cycle[x]=true;

         return true;

     }

     size[x]=;

     par[x]=p;

     bool flag=false;

     for(unsigned i=;i<e[x].size();i++) {

         int &y=e[x][i].to;

         if(y==p||on_cycle[y]) continue;

         if(dfs1(y,x)) {

             par[x]=;

             id[y]=++cnt;

             w[cnt]=e[x][i].w;

             if(on_cycle[x]) {

                 flag=true;

             } else {

                 on_cycle[x]=true;

             }

         } else {

             size[x]+=size[y];

             if(size[y]>size[son[x]]) son[x]=y;

         }

     }

     if(on_cycle[x]) cyc[++cnt_cyc]=x;

     return on_cycle[x]^flag;

 }

 int rt;

 void dfs2(const int x) {

     dep[x]=dep[par[x]]+;

     top[x]=x==son[par[x]]?top[par[x]]:x;

     root[x]=cyc[rt];

     if(son[x]) {

         id[son[x]]=++cnt;

         dfs2(son[x]);

     }

     for(unsigned i=;i<e[x].size();i++) {

         int &y=e[x][i].to;

         if(y==par[x]||on_cycle[y]) continue;

         if(y==son[x]) {

             w[id[y]]=e[x][i].w;

             continue;

         }

         id[y]=++cnt;

         w[cnt]=e[x][i].w;

         dfs2(y);

     }

 }

 void dfs3(const int x,const int p) {

     par[x]=p;

     son[x]=;

     size[x]=;

     for(unsigned i=;i<e[x].size();i++) {

         int &y=e[x][i].to;

         if(y==p||on_cycle[y]) continue;

         dfs3(y,x);

         size[x]+=size[y];

         if(size[y]>size[son[x]]) son[x]=y;

     }

 }

 class SegmentTree {

     private:

         int left[V<<],right[V<<];

         long long sum[V<<],submax[V<<],submin[V<<],premax[V<<],premin[V<<],sufmax[V<<],sufmin[V<<];

         bool neg[V<<];

         int sz,newnode() {

             return ++sz;

         }

         void negate(long long &x) {

             x=-x;

         }

         void reverse(const int p) {

             negate(sum[p]);

             negate(submax[p]);

             negate(submin[p]);

             std::swap(submax[p],submin[p]);

             negate(premax[p]);

             negate(premin[p]);

             std::swap(premax[p],premin[p]);

             negate(sufmax[p]);

             negate(sufmin[p]);

             std::swap(sufmax[p],sufmin[p]);

         }

         void push_up(const int p) {

             sum[p]=sum[left[p]]+sum[right[p]];

             submax[p]=std::max(std::max(submax[left[p]],submax[right[p]]),sufmax[left[p]]+premax[right[p]]);

             submin[p]=std::min(std::min(submin[left[p]],submin[right[p]]),sufmin[left[p]]+premin[right[p]]);

             premax[p]=std::max(premax[left[p]],sum[left[p]]+premax[right[p]]);

             premin[p]=std::min(premin[left[p]],sum[left[p]]+premin[right[p]]);

             sufmax[p]=std::max(sufmax[right[p]],sum[right[p]]+sufmax[left[p]]);

             sufmin[p]=std::min(sufmin[right[p]],sum[right[p]]+sufmin[left[p]]);

         }

         void push_down(const int p) {

             if(!neg[p]) return;

             reverse(left[p]);

             reverse(right[p]);

             neg[p]=false;

             neg[left[p]]=!neg[left[p]];

             neg[right[p]]=!neg[right[p]];

         }

     public:

         struct Ans {

             long long sum,pre,sub,suf;

         };

         int root;

         void build(int &p,const int b,const int e) {

             p=newnode();

             if(b==e) {

                 sum[p]=w[b];

                 submax[p]=premax[p]=sufmax[p]=std::max(w[b],);

                 submin[p]=premin[p]=sufmin[p]=std::min(w[b],);

                 return;

             }

             int mid=(b+e)>>;

             build(left[p],b,mid);

             build(right[p],mid+,e);

             push_up(p);

         }

         void modify(const int p,const int b,const int e,const int l,const int r) {

             if((b==l)&&(e==r)) {

                 reverse(p);

                 neg[p]=!neg[p];

                 return;

             }

             push_down(p);

             int mid=(b+e)>>;

             if(l<=mid) modify(left[p],b,mid,l,std::min(mid,r));

             if(r>mid) modify(right[p],mid+,e,std::max(mid+,l),r);

             push_up(p);

         }

         Ans query(const int p,const int b,const int e,const int l,const int r) {

             if((b==l)&&(e==r)) {

                 return (Ans){sum[p],premax[p],submax[p],sufmax[p]};

             }

             push_down(p);

             int mid=(b+e)>>;

             long long leftsum=,leftpre=,leftsub=,leftsuf=,rightsum=,rightpre=,rightsub=,rightsuf=;

             if(l<=mid) {

                 Ans tmp=query(left[p],b,mid,l,std::min(mid,r));

                 leftsum=tmp.sum;

                 leftpre=tmp.pre;

                 leftsub=tmp.sub;

                 leftsuf=tmp.suf;

             }

             if(r>mid) {

                 Ans tmp=query(right[p],mid+,e,std::max(mid+,l),r);

                 rightsum=tmp.sum;

                 rightpre=tmp.pre;

                 rightsub=tmp.sub;

                 rightsuf=tmp.suf;

             }

             long long sum,pre,sub,suf;

             sum=leftsum+rightsum;

             pre=std::max(leftpre,leftsum+rightpre);

             sub=std::max(std::max(leftsub,rightsub),leftsuf+rightpre);

             suf=std::max(rightsuf,rightsum+leftsuf);

             return (Ans){sum,pre,sub,suf};

         }

 };

 SegmentTree t;

 int n;

 inline void modify(int x,int y) {

     if(root[x]!=root[y]) {

         while(top[x]!=root[x]) {

             t.modify(t.root,,n,id[top[x]],id[x]);

             x=par[top[x]];

         }

         if(x!=top[x]) {

             t.modify(t.root,,n,id[son[top[x]]],id[x]);

             x=top[x];

         }

         while(top[y]!=root[y]) {

             t.modify(t.root,,n,id[top[y]],id[y]);

             y=par[top[y]];

         }

         if(y!=top[y]) {

             t.modify(t.root,,n,id[son[top[y]]],id[y]);

             y=top[y];

         }

     } else {

         while(top[x]!=top[y]) {

             if(dep[top[x]]<dep[top[y]]) std::swap(x,y);

             t.modify(t.root,,n,id[top[x]],id[x]);

             x=par[top[x]];

         }

         if(x!=y) {

             if(dep[x]<dep[y]) std::swap(x,y);

             t.modify(t.root,,n,id[son[y]],id[x]);

         }

         return;

     }

     if((id[y]-id[x]+cnt_cyc)%cnt_cyc>(id[x]-id[y]+cnt_cyc)%cnt_cyc) std::swap(x,y);

     if(id[x]<id[y]) {

         t.modify(t.root,,n,id[x],id[y]-);

     } else {

         t.modify(t.root,,n,id[x],cnt_cyc);

         if(id[y]!=) t.modify(t.root,,n,,id[y]-);

     }

 }

 inline long long query(int x,int y) {

     long long lastsum=,lastpre=,lastsub=,lastsuf=,nextsum=,nextpre=,nextsub=,nextsuf=;

     long long ans=;

     if(root[x]!=root[y]) {

         while(top[x]!=root[x]) {

             SegmentTree::Ans tmp=t.query(t.root,,n,id[top[x]],id[x]);

             lastsub=std::max(std::max(lastsub,tmp.sub),lastpre+tmp.suf);

             lastpre=std::max(tmp.pre,lastpre+tmp.sum);

             lastsuf=std::max(lastsuf,lastsum+tmp.suf);

             lastsum+=tmp.sum;

             ans=std::max(ans,lastsub);

             x=par[top[x]];

         }

         if(x!=top[x]) {

             SegmentTree::Ans tmp=t.query(t.root,,n,id[son[top[x]]],id[x]);

             lastsub=std::max(std::max(lastsub,tmp.sub),lastpre+tmp.suf);

             lastpre=std::max(tmp.pre,lastpre+tmp.sum);

             lastsuf=std::max(lastsuf,lastsum+tmp.suf);

             lastsum+=tmp.sum;

             ans=std::max(ans,lastsub);

             x=top[x];

         }

         while(top[y]!=root[y]) {

             SegmentTree::Ans tmp=t.query(t.root,,n,id[top[y]],id[y]);

             nextsub=std::max(std::max(nextsub,tmp.sub),nextpre+tmp.suf);

             nextpre=std::max(tmp.pre,nextpre+tmp.sum);

             nextsuf=std::max(nextsuf,nextsum+tmp.suf);

             nextsum+=tmp.sum;

             ans=std::max(ans,nextsub);

             y=par[top[y]];

         }

          if(y!=top[y]) {

             SegmentTree::Ans tmp=t.query(t.root,,n,id[son[top[y]]],id[y]);

             nextsub=std::max(std::max(nextsub,tmp.sub),nextpre+tmp.suf);

             nextpre=std::max(tmp.pre,nextpre+tmp.sum);

             nextsuf=std::max(nextsuf,nextsum+tmp.suf);

             nextsum+=tmp.sum;

             ans=std::max(ans,nextsub);

             y=top[y];

         }

     } else {

         while(top[x]!=top[y]) {

             if(dep[top[x]]<dep[top[y]]) {

                 std::swap(x,y);

                 std::swap(lastsum,nextsum);

                 std::swap(lastsub,nextsub);

                 std::swap(lastpre,nextpre);

                 std::swap(lastsuf,nextsuf);

             }

             SegmentTree::Ans tmp=t.query(t.root,,n,id[top[x]],id[x]);

             lastsub=std::max(std::max(lastsub,tmp.sub),lastpre+tmp.suf);

             lastpre=std::max(tmp.pre,lastpre+tmp.sum);

             lastsuf=std::max(lastsuf,lastsum+tmp.suf);

             lastsum+=tmp.sum;

             ans=std::max(ans,lastsub);

             x=par[top[x]];

         }

         if(x!=y) {

             if(dep[x]<dep[y]) {

                 std::swap(x,y);

                 std::swap(lastsum,nextsum);

                 std::swap(lastsub,nextsub);

                 std::swap(lastpre,nextpre);

                 std::swap(lastsuf,nextsuf);

             }

             SegmentTree::Ans tmp=t.query(t.root,,n,id[son[y]],id[x]);

             lastsub=std::max(std::max(lastsub,tmp.sub),lastpre+tmp.suf);

             lastpre=std::max(tmp.pre,lastpre+tmp.sum);

             lastsuf=std::max(lastsuf,lastsum+tmp.suf);

             lastsum+=tmp.sum;

         }

         ans=std::max(ans,std::max(lastsub,lastpre+nextpre));

         return ans;

     }

     if((id[y]-id[x]+cnt_cyc)%cnt_cyc>(id[x]-id[y]+cnt_cyc)%cnt_cyc) {

         std::swap(x,y);

         std::swap(lastsum,nextsum);

         std::swap(lastsub,nextsub);

         std::swap(lastpre,nextpre);

         std::swap(lastsuf,nextsuf);

     }

     SegmentTree::Ans tmp;

     if(id[x]<id[y]) {

         tmp=t.query(t.root,,n,id[x],id[y]-);

     } else {

         SegmentTree::Ans tmp1,tmp2;

         tmp1=t.query(t.root,,n,id[x],cnt_cyc);

         if(id[y]!=) tmp2=t.query(t.root,,n,,id[y]-);

         if(id[y]!=) {

             tmp.sum=tmp1.sum+tmp2.sum;

             tmp.sub=std::max(std::max(tmp1.sub,tmp2.sub),tmp1.suf+tmp2.pre);

             tmp.pre=std::max(tmp1.pre,tmp1.sum+tmp2.pre);

             tmp.suf=std::max(tmp2.suf,tmp2.sum+tmp1.suf);

         } else {

             tmp=tmp1;

         }

     }

     ans=std::max(ans,tmp.sub);

     ans=std::max(ans,lastpre+tmp.pre);

     ans=std::max(ans,nextpre+tmp.suf);

     ans=std::max(ans,lastpre+nextpre+tmp.sum);

     return ans;

 }

 int main() {

     n=getint();

     for(int i=;i<=n;i++) {

         int u=getint(),v=getint(),w=getint();

         add_edge(u,v,w);

         add_edge(v,u,w);

     }

     dfs1(,);

     for(rt=;rt<=cnt_cyc;rt++) {

         if(rt==cnt_cyc) dfs3(cyc[rt],);

         dfs2(cyc[rt]);

     }

     t.build(t.root,,n);

     for(int m=getint();m;m--) {

         char op[];

         scanf("%1s",op);

         switch(op[]) {

             case 'f': {

                 int x=getint(),y=getint();

                 modify(x,y);

                 break;

             }

             case '?': {

                 int x=getint(),y=getint();

                 printf("%lld\n",query(x,y));

                 break;

             }

         }

     }

     return ;

 }

附数据生成器：

 #include<ctime>

 #include<vector>

 #include<cstdio>

 #include<cstdlib>

 const int V=;

 std::vector<int> e[V];

 inline void add_edge(const int u,const int v) {

     e[u].push_back(v);

 }

 int par[V],dep[V],top[V],son[V],size[V];

 void dfs1(const int x) {

     size[x]=;

     dep[x]=dep[par[x]]+;

     for(unsigned i=;i<e[x].size();i++) {

         int &y=e[x][i];

         dfs1(y);

         size[x]+=size[y];

         if(size[y]>size[son[x]]) son[x]=y;

     }

 }

 void dfs2(const int x) {

     top[x]=x==son[par[x]]?top[par[x]]:x;

     for(unsigned i=;i<e[x].size();i++) {

         int &y=e[x][i];

         dfs2(y);

     }

 }

 inline int get_lca(int x,int y) {

     while(top[x]!=top[y]) {

         if(dep[top[x]]<dep[top[y]]) std::swap(x,y);

         x=par[top[x]];

     }

     if(dep[x]<dep[y]) std::swap(x,y);

     return y;

 }

 int main() {

     srand(time(NULL));

     int n=,m=,w=;

     printf("%d\n",n);

     for(int i=;i<=n;i++) {

         printf("%d %d %d\n",par[i]=rand()%(i-)+,i,rand()%w-w/);

         add_edge(par[i],i);

     }

     dfs1();

     dfs2();

     for(int i=;i<n;i++) {

         if(i!=par[n]) {

             int lca=get_lca(i,n);

             if((dep[i]+dep[n]-dep[lca]*)&) continue;

             printf("%d %d %d\n",i,n,rand()%w-w/);

             break;

         }

     }

     printf("%d\n",m);

     for(int i=;i<=m;i++) {

         int op=rand()%;

         if(op) {

             int y=rand()%(n-)+;

             int x=rand()%(y-)+;

             printf("? %d %d\n",x,y);

         } else {

             int y=rand()%(n-)+;

             int x=rand()%(y-)+;

             printf("f %d %d\n",x,y);

         }

     }

     return ;

 }

最新文章

  1. vue-loader配合webpack的使用及安装
  2. 使用 Async 和 Await 的异步编程（C# 和 Visual Basic）[msdn.microsoft.com]
  3. MIUI5(红米、小米)打开开发者模式
  4. JStorm集群的安装和使用
  5. 再见Unity3d的死循环
  6. Nginx学习笔记（六） 源码分析&amp;启动过程
  7. 导出websphere内存镜像
  8. mycat配置日志
  9. 团队项目——NABC
  10. C C++实现创建目录
  11. 求教。。 为什么加载到servlet页面显示空白或者一直加载页面没显示也没错误？
  12. WebClient外部请求乱码
  13. hive与hbase的区别与联系
  14. shell脚本修复MySQL主从同步
  15. HTML简单介绍及常见元素
  16. Ubuntu下搜狗输入法突然无法输入中文
  17. 基于Excel参数化你的Selenium2测试代码
  18. PowerBI开发 第四篇：DAX表达式
  19. Linux-#!/bin/sh理解
  20. SQL语句在数据库中可以执行在mybatis执行不了

热门文章

  1. rollup&amp;&amp;cube
  2. ADB常用命令（二）
  3. Linux下获取和设置IP
  4. HTML5 localStorage、sessionStorage 作用域
  5. Java KeyStore 用命令生成keystore文件自己生成证书，简介
  6. 配置vuejs加载模拟数据
  7. 删除数据库所有存储过程的SQL语句
  8. Django和Mysql合用时，显示时间问题
  9. HTML/CSS权值继承
  10. C语言：凯撒密码的实现