题目大意：
给定一个环长为奇数的带权基环树，支持以下两种操作：
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 ;
}