题目内容:
Ray 乐忠于旅游,这次他来到了T 城。T 城是一个水上城市,一共有 N 个景点,有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本,T 城的任意两个景点之间有且只有一条路径。换句话说, T 城中只有N − 1 座桥。Ray 发现,有些桥上可以看到美丽的景色,让人心情愉悦,但有些桥狭窄泥泞,令人烦躁。于是,他给每座桥定义一个愉悦度w,也就是说,Ray 经过这座桥会增加w 的愉悦度,这或许是正的也可能是负的。有时,Ray 看待同一座桥的心情也会发生改变。现在,Ray 想让你帮他计算从u 景点到v 景点能获得的总愉悦度。有时,他还想知道某段路上最美丽的桥所提供的最大愉悦度,或是某段路上最糟糕的一座桥提供的最低愉悦度。
题目分析:
一道码农题,最难的地方在于如何判断输入的是哪个操作,所以要深刻掌握switch,下面我来讲讲switch的用法。
switch的主要结构是:
switch(a){
case x:{......;break;}
case y:{......;break;}
default:{.......}
}
值得注意的是case可以写任意多个且不能像if那样进行大于小于等的比较,所以switch的用处没有if大,而且switch可以完全用if代替,但是switch可以更方便地判断数字是否是这个并且作出操作。考虑到编程习惯,所以switch中case后面的括号是可以省略的。
题目代码:
#include<bits/stdc++.h>
#define SUM t[now].sum
#define MIN t[now].minn
#define MAX t[now].maxx
using namespace std;
struct edge{
int to,w;
};
const int INF = ;
const int maxn = ;
vector <edge> g[maxn];
int d[maxn],arr[maxn],fa[maxn],son[maxn],head[maxn],sz[maxn],num[maxn],dep[maxn];
int to_fa[maxn],fto_fa[maxn];
struct ed{int from,to;};
vector <ed> edges;
void dfs1(int now,int f,int d){
arr[now] = ;
dep[now] = d;
fa[now] = f;
sz[now] = ;
int maxx = ;
for(int i=;i<g[now].size();i++){
if(arr[g[now][i].to]){
to_fa[now] = i;
continue;
}
fto_fa[g[now][i].to] = i;
dfs1(g[now][i].to,now,d+);
sz[now] += sz[g[now][i].to];
if(sz[g[now][i].to] > maxx){
maxx = sz[g[now][i].to];
son[now] = g[now][i].to;
}
}
} int a[];
int bh = ; void dfs2(int now,int h){
arr[now] = ;
head[now] = h;
for(int i=;i<g[now].size();i++){
if(g[now][i].to == son[now]&&!arr[g[now][i].to]){
num[now] = ++bh;
a[bh] = g[now][i].w;
dfs2(g[now][i].to,h);
break;
}
}
for(int i=;i<g[now].size();i++){
if(g[now][i].to != son[now] && arr[g[now][i].to]==){
dfs2(g[now][i].to,g[now][i].to);
}
}
}
struct node{
int sum,minn,maxx;
int f;
}t[];
void push_down(int);
void push_up(int now){
if(t[now].f)push_down(now);
if(t[now * ].f) push_down(now*);
if(t[now*+].f)push_down(now*+);
SUM = t[now * ].sum + t[now * + ].sum;
MIN = min(t[now * ].minn,t[now*+].minn);
MAX = max(t[now*].maxx,t[now*+].maxx);
} void build_tree(int l,int r,int now){
if(l == r){
SUM = MAX = MIN = a[l];
return;
}
int mid = (l+r) >> ;
build_tree(l,mid,now * );
build_tree(mid+,r,now * + );
push_up(now);
} void push_down(int now){
SUM = -SUM;
swap(MIN,MAX);
MIN = -MIN;
MAX = -MAX;
t[now * ].f ^= ;
t[now * + ].f ^=;
t[now].f = ;
} struct ask{
int u,v,dir;
}A[];
int pre[];
struct point{
int dis,num;
};
vector <point> lca[];
int get_l[];
int found(int x){
int rx = x;
while(pre[rx]!=rx)rx = pre[rx];
while(pre[x]!=rx){
int temp = pre[x];
pre[x] = rx;
x = temp;
}
return rx;
}
void tarjan(int now,int fa){
arr[now] = ;
for(int i=;i<lca[now].size();i++){
if(arr[lca[now][i].dis]){
get_l[lca[now][i].num] = found(lca[now][i].dis);
}
}
for(int i=;i<g[now].size();i++){
if(arr[g[now][i].to]) continue;
tarjan(g[now][i].to,now);
}
pre[found(now)] = found(fa);
} void change(int l,int r,int c,int delta,int now){
if(t[now].f) push_down(now);
if(l == c && r == c){
SUM = delta;
MIN = delta;
MAX = delta;
return;
}
int mid = (l+r) >> ;
if(c <= mid)change(l,mid,c,delta,now * );
else change(mid+,r,c,delta,now * + );
push_up(now);
}
void opp(int l,int r,int begin,int end,int now){//[l,r]树,[begin,end]询问
if(t[now].f) push_down(now);
if(begin>r||end<l||begin>end)return;
if(l>=begin&&r<=end){
t[now].f ^=;
if(t[now].f)push_down(now);
return;
}
int mid = (l + r) >> ;
opp(l,mid,begin,end,now*);
opp(mid+,r,begin,end,now*+);
push_up(now);
} struct stru{int sum,max,min;}; stru merge(stru a,stru b){
stru c = (stru){a.sum+b.sum,max(a.max,b.max),min(a.min,b.min)};
return c;
} stru get_sum(int l,int r,int begin,int end,int now){
if(t[now].f) push_down(now);
if(begin > r || end < l||begin>end) return (stru){,-INT_MAX,INT_MAX};
if(l >= begin && r <= end){
return (stru){SUM,MAX,MIN};
}
int mid = (l+r) >> ;
stru ans = get_sum(l,mid,begin,end,now * );
ans = merge(ans,get_sum(mid+,r,begin,end,now*+));
push_up(now);
return ans;
} int main(){
ios::sync_with_stdio(false);
int n; cin >> n;
edges.push_back((ed){,});
for(int i=;i<n;i++){
int x,y,w;
cin >> x >> y >> w;
x++;y++;
edges.push_back((ed){x,y});
g[x].push_back((edge){y,w});
g[y].push_back((edge){x,w});
}
dfs1(,-,);
memset(arr,,sizeof(arr));
dfs2(,);
build_tree(,bh,);
int m;cin >> m;
for(int i=;i<=m;i++){
string str; cin >> str;
if(str[] == 'C') A[i].dir = ;
if(str[] == 'N') A[i].dir = ;
if(str[] == 'S') A[i].dir = ;
if(str[] == 'A') A[i].dir = ;
if(str[] == 'I') A[i].dir = ;
int u,v; cin >> u >> v;
if(A[i].dir!=)u++,v++;
A[i].u = u;
A[i].v = v;
if(A[i].dir == ) continue;
lca[u].push_back((point){v,i});
lca[v].push_back((point){u,i});
}
memset(arr,,sizeof(arr));
for(int i=;i<=n;i++) pre[i] = i;
tarjan(,-);
for(int i=;i<=m;i++){
if(A[i].dir == ){
int u = edges[A[i].u].from;
int v = edges[A[i].u].to;
if(fa[v] != u) swap(u,v);
if(son[u] == v){
int h = head[v];
int bg = num[h];
int ch = dep[u]-dep[h];
bg = bg + ch;
change(,bh,bg,A[i].v,);
}else{
int e = to_fa[v];
int ne = fto_fa[v];
g[u][ne].w = A[i].v;
g[v][e].w = A[i].v;
}
continue;
}
int lac = get_l[i];
int s = A[i].u,t = A[i].v;
if(dep[s]<=dep[t])swap(s,t);
if(A[i].dir == ){
while(s!=lac && dep[s] > dep[lac]){
int h = head[s];
if(h == s){
int e = to_fa[s];
int ne = fto_fa[s];
g[fa[s]][ne].w = -g[fa[s]][ne].w;
g[s][e].w = -g[s][e].w;
s = fa[s];
continue;
}
int bg = num[h];
if(dep[h] >= dep[lac]){
int ch = dep[s]-dep[h]-;
int end = bg + ch;
opp(,bh,bg,end,);
s = h;
}else{
bg = num[lac];
int ch = dep[s]-dep[lac]-;
int end = bg + ch;
opp(,bh,bg,end,);
s = lac;
break;
}
}
while(t!=lac&&dep[t] > dep[lac]){
int h = head[t];
if(h == t){
int e = to_fa[t];
int ne = fto_fa[t];
g[fa[t]][ne].w = -g[fa[t]][ne].w;
g[t][e].w = -g[t][e].w;
t = fa[t];
continue;
}
int bg = num[h];
if(dep[h] > dep[lac]){
int ch = dep[t]-dep[h]-;
int end = bg + ch;
opp(,bh,bg,end,);
t = h;
}else{
bg = num[lac];
int ch = dep[t]-dep[lac]-;
int end = bg+ch;
opp(,bh,bg,end,);
break;
}
}
continue;
}
int &pd = A[i].dir;
if(pd == ||pd == ||pd == ){
int ans = ;
if(pd == ) ans = INT_MAX;
if(pd == ) ans = -INT_MAX;
while(s!=lac&&dep[s] > dep[lac]){
int h = head[s];
if(h == s){
int e = to_fa[s];
if(pd == ) ans += g[s][e].w;
else if(pd == ) ans = max(ans,g[s][e].w);
else ans = min(ans,g[s][e].w);
s = fa[s];
continue;
}
int bg = num[h];
if(dep[h] >= dep[lac]){
int ch = dep[s] - dep[h] - ;
int end = bg + ch;
stru p = get_sum(,bh,bg,end,);
if(pd == ) ans += p.sum;
else if(pd == ) ans = max(ans,p.max);
else ans = min(ans,p.min);
s = h;
}else{
bg = num[lac];
int ch = dep[s] - dep[lac] - ;
int end = bg + ch;
stru p = get_sum(,bh,bg,end,);
if(pd == ) ans += p.sum;
else if(pd == ) ans = max(ans,p.max);
else ans = min(ans,p.min);
s = lac;
break;
}
}
while(t!=lac&&dep[t] > dep[lac]){
int h = head[t];
if(h == t){
int e = to_fa[t];
if(pd == ) ans += g[t][e].w;
else if(pd == ) ans = max(ans,g[t][e].w);
else ans = min(ans,g[t][e].w);
t = fa[t];
continue;
}
int bg = num[h];
if(dep[h] > dep[lac]){
int ch = dep[t] - dep[h] - ;
int end = bg + ch;
stru p = get_sum(,bh,bg,end,);
if(pd == ) ans += p.sum;
else if(pd == ) ans = max(ans,p.max);
else ans = min(ans,p.min);
t = h;
}else{
bg = num[lac];
int ch = dep[t] - dep[lac] - ;
int end = bg + ch;
stru p = get_sum(,bh,bg,end,);
if(pd == ) ans += p.sum;
else if(pd == ) ans = max(ans,p.max);
else ans = min(ans,p.min);
break;
}
}
printf("%d\n",ans);
}
}
return ;
}