题意:在spoj375基础上增加了一条路径的取反操作,其他都一样。
思路:剖分没有变化,在线段树部分,需要一个tag标记该段是否需要需要取反,记录一个最大值、最小值即可。= =(打tag的那
段应该已经跟新好,push_down的时候如果tag=1那么直接对两个子段进行更新。。一开始意识模糊了。。)详见代码:
/********************************************************* file name: poj3237.cpp author : kereo create time: 2015年01月21日 星期三 10时15分39秒 *********************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<set> #include<map> #include<vector> #include<stack> #include<cmath> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int sigma_size=26; const int N=50; const int MAXN=10000+50; const int inf=0x3fffffff; const double eps=1e-8; const int mod=100000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) #define PII pair<int, int> #define mk(x,y) make_pair((x),(y)) int n,edge_cnt,cnt; char str[N]; int head[MAXN],sz[MAXN],dep[MAXN],son[MAXN],fa[MAXN],top[MAXN],pos[MAXN]; struct Edge{ int u,v,w,next; }edge[MAXN<<1]; struct node{ int l,r; int tag,Min,Max; }segtree[MAXN<<2]; void init(){ edge_cnt=cnt=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w){ edge[edge_cnt].u=u; edge[edge_cnt].v=v; edge[edge_cnt].w=w; edge[edge_cnt].next=head[u]; head[u]=edge_cnt++; } void dfs1(int u,int pre,int depth){ sz[u]=1; son[u]=0; dep[u]=depth; fa[u]=pre; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v == pre) continue; dfs1(v,u,depth+1); sz[u]+=sz[v]; if(sz[son[u]]<sz[v]) son[u]=v; } } void dfs2(int u,int tp){ pos[u]=cnt++; top[u]=tp; if(son[u]!=0) dfs2(son[u],top[u]); for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v == fa[u] || v == son[u]) continue; dfs2(v,v); } } void build(int rt,int l,int r){ segtree[rt].l=l; segtree[rt].r=r; segtree[rt].tag=0; segtree[rt].Min=inf; segtree[rt].Max=-inf; if(l == r) return ; int mid=(l+r)>>1; build(L(rt),l,mid); build(R(rt),mid+1,r); } void push_down(int rt){ if(segtree[rt].l == segtree[rt].r) return ; if(segtree[rt].tag){ segtree[rt].tag=0; segtree[L(rt)].tag^=1; segtree[R(rt)].tag^=1; swap(segtree[L(rt)].Max,segtree[L(rt)].Min); segtree[L(rt)].Max*=-1; segtree[L(rt)].Min*=-1; swap(segtree[R(rt)].Max,segtree[R(rt)].Min); segtree[R(rt)].Max*=-1; segtree[R(rt)].Min*=-1; } } void push_up(int rt){ segtree[rt].Max=max(segtree[L(rt)].Max,segtree[R(rt)].Max); segtree[rt].Min=min(segtree[L(rt)].Min,segtree[R(rt)].Min); } void update(int rt,int p,int x){ if(segtree[rt].l == segtree[rt].r){ segtree[rt].tag=0; segtree[rt].Max=segtree[rt].Min=x; return ; } push_down(rt); int mid=(segtree[rt].l+segtree[rt].r)>>1; if(p<=mid) update(L(rt),p,x); else update(R(rt),p,x); push_up(rt); } void Negate(int rt,int l,int r){ if(segtree[rt].l == l && segtree[rt].r == r){ segtree[rt].tag^=1; swap(segtree[rt].Max,segtree[rt].Min); segtree[rt].Min*=-1; segtree[rt].Max*=-1; return ; } push_down(rt); int mid=(segtree[rt].l+segtree[rt].r)>>1; if(r<=mid) Negate(L(rt),l,r); else if(l>mid) Negate(R(rt),l,r); else{ Negate(L(rt),l,mid); Negate(R(rt),mid+1,r); } push_up(rt); } int query(int rt,int l,int r){ if(segtree[rt].l ==l && segtree[rt].r == r) return segtree[rt].Max; push_down(rt); int mid=(segtree[rt].l+segtree[rt].r)>>1; if(r<=mid) return query(L(rt),l,r); else if(l>mid) return query(R(rt),l,r); else return max(query(L(rt),l,mid),query(R(rt),mid+1,r)); push_up(rt); } int solve(int id,int u,int v){ int ans=-inf; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); if(id == 1) ans=max(ans,query(1,pos[top[u]],pos[u])); else Negate(1,pos[top[u]],pos[u]); u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); if(u!=v){ if(id == 1) ans=max(ans,query(1,pos[u]+1,pos[v])); else Negate(1,pos[u]+1,pos[v]); } return ans; } int main(){ int T; scanf("%d",&T); while(T--){ init(); scanf("%d",&n); for(int i=1;i<n;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dfs1(1,1,1); dfs2(1,1); build(1,1,n-1); for(int i=0;i<edge_cnt;i+=2){ int u=edge[i].u,v=edge[i].v,w=edge[i].w; if(dep[u]<dep[v]) swap(u,v); update(1,pos[u],w); } while(1){ scanf("%s",str); if(str[0] == 'D') break; if(str[0] == 'C'){ int x,w; scanf("%d%d",&x,&w); x=(x-1)*2; int u=edge[x].u,v=edge[x].v; if(dep[u]<dep[v]) swap(u,v); update(1,pos[u],w); } if(str[0] == 'Q'){ int u,v; scanf("%d%d",&u,&v); printf("%d\n",solve(1,u,v)); } if(str[0] == 'N'){ int u,v; scanf("%d%d",&u,&v); solve(2,u,v); } } } return 0; }