题目大意：

　　给定一个环长为奇数的带权基环树，支持以下两种操作：

　　　　1.两点间最短路取反；

　　　　2.两点间最短路求最大子段和。

思路：

　　首先找出环，然后对每一个外向树轻重链剖分，

　　用线段树维护每一个区间的和、前缀和最值、后缀和最值及子段最值。

　　每次修改时，分下列两种情况讨论：

　　　　1.两个点在同一棵外向树上，按照普通的树链剖分修改，线段树上打取反的标记。

　　　　2.两个点再不同外向树上，先各自沿着链往上跳，然后都跳到环上的时候，可以将两个点在环中的序号减一减，对环长取模，看看哪个小。

　　查询时大致和修改一样，但是合并两个区间的时候很麻烦，要注意考虑完全。

细节：

　　1.找环可以在DFS的时候和树剖一起完成，也可以用并查集写，两个效率差不多。

　　2.标记可以打好几次，所以不能简单地把标记赋值为true，而是每次取反。

这题代码量比较大，vjudge上除了周骏东都是10K左右。网上的题解也很少，中英文都没有找到。

一开始写挂的地方特别多，对拍对了好多次才排出所有的错。

 

1 #include
     
        2 #include
      
         3 #include
       
          4 inline int getint() {  5     char ch;  6     bool neg=false;  7     while(!isdigit(ch=getchar())) if(ch=='-') neg=true;  8     int x=ch^'0';  9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10     return neg?-x:x; 11 } 12 const int V=100001; 13 struct Edge { 14     int to,w; 15 }; 16 std::vector
        
          e[V]; 17 inline void add_edge(const int u,const int v,const int w) { 18     e[u].push_back((Edge){v,w}); 19 } 20 int par[V],size[V],son[V],cyc[V],id[V],w[V],root[V],dep[V],top[V]; 21 int cnt_cyc,cnt; 22 bool on_cycle[V]; 23 bool dfs1(const int x,const int p) { 24     if(par[x]||(x==1&&p!=0)) { 25         on_cycle[x]=true; 26         return true; 27     }  28     size[x]=1; 29     par[x]=p; 30     bool flag=false; 31     for(unsigned i=0;i
         
          size[son[x]]) son[x]=y; 46         } 47     } 48     if(on_cycle[x]) cyc[++cnt_cyc]=x; 49     return on_cycle[x]^flag; 50 } 51 int rt; 52 void dfs2(const int x) { 53     dep[x]=dep[par[x]]+1; 54     top[x]=x==son[par[x]]?top[par[x]]:x; 55     root[x]=cyc[rt]; 56     if(son[x]) { 57         id[son[x]]=++cnt; 58         dfs2(son[x]); 59     } 60     for(unsigned i=0;i
          
           size[son[x]]) son[x]=y; 82 } 83 } 84 class SegmentTree { 85 private: 86 int left[V<<1],right[V<<1]; 87 long long sum[V<<1],submax[V<<1],submin[V<<1],premax[V<<1],premin[V<<1],sufmax[V<<1],sufmin[V<<1]; 88 bool neg[V<<1]; 89 int sz,newnode() { 90 return ++sz; 91 } 92 void negate(long long &x) { 93 x=-x; 94 } 95 void reverse(const int p) { 96 negate(sum[p]); 97 negate(submax[p]); 98 negate(submin[p]); 99 std::swap(submax[p],submin[p]);100 negate(premax[p]);101 negate(premin[p]);102 std::swap(premax[p],premin[p]);103 negate(sufmax[p]);104 negate(sufmin[p]);105 std::swap(sufmax[p],sufmin[p]);106 }107 void push_up(const int p) {108 sum[p]=sum[left[p]]+sum[right[p]];109 submax[p]=std::max(std::max(submax[left[p]],submax[right[p]]),sufmax[left[p]]+premax[right[p]]);110 submin[p]=std::min(std::min(submin[left[p]],submin[right[p]]),sufmin[left[p]]+premin[right[p]]);111 premax[p]=std::max(premax[left[p]],sum[left[p]]+premax[right[p]]);112 premin[p]=std::min(premin[left[p]],sum[left[p]]+premin[right[p]]);113 sufmax[p]=std::max(sufmax[right[p]],sum[right[p]]+sufmax[left[p]]);114 sufmin[p]=std::min(sufmin[right[p]],sum[right[p]]+sufmin[left[p]]);115 }116 void push_down(const int p) {117 if(!neg[p]) return;118 reverse(left[p]);119 reverse(right[p]);120 neg[p]=false;121 neg[left[p]]=!neg[left[p]];122 neg[right[p]]=!neg[right[p]];123 }124 public:125 struct Ans {126 long long sum,pre,sub,suf;127 };128 int root;129 void build(int &p,const int b,const int e) {130 p=newnode();131 if(b==e) {132 sum[p]=w[b];133 submax[p]=premax[p]=sufmax[p]=std::max(w[b],0);134 submin[p]=premin[p]=sufmin[p]=std::min(w[b],0);135 return;136 }137 int mid=(b+e)>>1;138 build(left[p],b,mid);139 build(right[p],mid+1,e);140 push_up(p);141 }142 void modify(const int p,const int b,const int e,const int l,const int r) {143 if((b==l)&&(e==r)) {144 reverse(p);145 neg[p]=!neg[p];146 return;147 }148 push_down(p);149 int mid=(b+e)>>1;150 if(l<=mid) modify(left[p],b,mid,l,std::min(mid,r));151 if(r>mid) modify(right[p],mid+1,e,std::max(mid+1,l),r);152 push_up(p);153 }154 Ans query(const int p,const int b,const int e,const int l,const int r) {155 if((b==l)&&(e==r)) {156 return (Ans){sum[p],premax[p],submax[p],sufmax[p]};157 }158 push_down(p);159 int mid=(b+e)>>1;160 long long leftsum=0,leftpre=0,leftsub=0,leftsuf=0,rightsum=0,rightpre=0,rightsub=0,rightsuf=0;161 if(l<=mid) {162 Ans tmp=query(left[p],b,mid,l,std::min(mid,r));163 leftsum=tmp.sum;164 leftpre=tmp.pre;165 leftsub=tmp.sub;166 leftsuf=tmp.suf;167 }168 if(r>mid) {169 Ans tmp=query(right[p],mid+1,e,std::max(mid+1,l),r);170 rightsum=tmp.sum;171 rightpre=tmp.pre;172 rightsub=tmp.sub;173 rightsuf=tmp.suf;174 }175 long long sum,pre,sub,suf;176 sum=leftsum+rightsum;177 pre=std::max(leftpre,leftsum+rightpre);178 sub=std::max(std::max(leftsub,rightsub),leftsuf+rightpre);179 suf=std::max(rightsuf,rightsum+leftsuf);180 return (Ans){sum,pre,sub,suf};181 }182 };183 SegmentTree t;184 int n;185 inline void modify(int x,int y) {186 if(root[x]!=root[y]) {187 while(top[x]!=root[x]) {188 t.modify(t.root,1,n,id[top[x]],id[x]);189 x=par[top[x]];190 }191 if(x!=top[x]) {192 t.modify(t.root,1,n,id[son[top[x]]],id[x]);193 x=top[x];194 }195 while(top[y]!=root[y]) {196 t.modify(t.root,1,n,id[top[y]],id[y]);197 y=par[top[y]];198 }199 if(y!=top[y]) {200 t.modify(t.root,1,n,id[son[top[y]]],id[y]);201 y=top[y];202 }203 } else {204 while(top[x]!=top[y]) {205 if(dep[top[x]]
           
            (id[x]-id[y]+cnt_cyc)%cnt_cyc) std::swap(x,y);216 if(id[x]
            
             (id[x]-id[y]+cnt_cyc)%cnt_cyc) {298 std::swap(x,y);299 std::swap(lastsum,nextsum);300 std::swap(lastsub,nextsub);301 std::swap(lastpre,nextpre);302 std::swap(lastsuf,nextsuf);303 }304 SegmentTree::Ans tmp;305 if(id[x]
            
           
          
         
        
       
      
     

 附数据生成器：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 const int V=100001; 6 std::vector
          
            e[V]; 7 inline void add_edge(const int u,const int v) { 8     e[u].push_back(v); 9 }10 int par[V],dep[V],top[V],son[V],size[V];11 void dfs1(const int x) {12     size[x]=1;13     dep[x]=dep[par[x]]+1;14     for(unsigned i=0;i
           
            size[son[x]]) son[x]=y;19 }20 }21 void dfs2(const int x) {22 top[x]=x==son[par[x]]?top[par[x]]:x;23 for(unsigned i=0;i