CF487ETourists圆方树套路题

CF487E Tourists

题目很套路&＃xff0c;现将利用点双建成圆方树&＃xff0c;对于每一个点双的方点用于存周边圆点的min&＃xff0c;方点需要用multiset维护圆点儿子的值&＃xff0c;当然也需要每个点维护自己的权值。

建树完成后基本就是树剖的板子了&＃xff0c;需要注意的是如果找到最后一点一个点事方点的话&＃xff0c;需要将方点的父亲进行统计


#include
#define inf 0x7fffffff
#define ll long long
//#define int long long
//#define double long double
#define re register int
#define void inline void
#define eps 1e-9
//#define mod 1e9&＃43;7
//#define ls(p) p<<1
//#define rs(p) p<<1|1
//#define pi acos(-1.0)
#define pb push_back
#define P pair < int , int >
#define mk make_pair
#define fi first
#define se second
#define unordered_map map
#define __int128 long long
#define x0 xx0
#define y0 yy0
using namespace std;
const int mod&＃61;1e9&＃43;7;
const int N&＃61;8e5&＃43;5;
int n,m,q,all;
multiset < int > SM[N];
int w[N];
namespace SEG
{#define ls(p) p<<1#define rs(p) p<<1|1int sum[N],a[N];void push(int p){sum[p]&＃61;min(sum[ls(p)],sum[rs(p)]);}void bulid(int p,int l,int r){if(l&＃61;&＃61;r){sum[p]&＃61;a[l];return;}int mid&＃61;(l&＃43;r)>>1;bulid(ls(p),l,mid);bulid(rs(p),mid&＃43;1,r);push(p);}void update(int p,int l,int r,int pos,int val){if(l&＃61;&＃61;r){sum[p]&＃61;val;return;}int mid&＃61;(l&＃43;r)>>1;if(pos<&＃61;mid) update(ls(p),l,mid,pos,val);else update(rs(p),mid&＃43;1,r,pos,val);push(p);}int ask(int p,int l,int r,int L,int R){if(L<&＃61;l&&r<&＃61;R) return sum[p];int mid&＃61;(l&＃43;r)>>1;int ans&＃61;1e9;if(L<&＃61;mid) ans&＃61;min(ans,ask(ls(p),l,mid,L,R));if(mid<R) ans&＃61;min(ans,ask(rs(p),mid&＃43;1,r,L,R));return ans;}#undef ls#undef rs
}
namespace GP2
{struct node{int ver,next;}e[N];int tot&＃61;1,head[N];int d[N],top[N],dfn[N],sz[N],son[N],fa[N];int num;void add(int x,int y){e[&＃43;&＃43;tot].ver&＃61;y;e[tot].next&＃61;head[x];head[x]&＃61;tot;}void addedge(int x,int y){add(x,y);add(y,x);}void dfs1(int x,int pre){int ma&＃61;-1;sz[x]&＃61;1;d[x]&＃61;d[pre]&＃43;1;fa[x]&＃61;pre;for(re i&＃61;head[x];i;i&＃61;e[i].next){int y&＃61;e[i].ver;if(y&＃61;&＃61;pre) continue;dfs1(y,x);sz[x]&＃43;&＃61;sz[y];if(sz[y]>ma) son[x]&＃61;y,ma&＃61;sz[y];}}void dfs2(int x,int pre){dfn[x]&＃61;&＃43;&＃43;num;top[x]&＃61;pre;if(!son[x]) return;dfs2(son[x],pre);for(re i&＃61;head[x];i;i&＃61;e[i].next){int y&＃61;e[i].ver;if(y&＃61;&＃61;son[x]||y&＃61;&＃61;fa[x]) continue;dfs2(y,y);}}void init(){dfs1(1,0);dfs2(1,1);for(re i&＃61;1;i<&＃61;n;i&＃43;&＃43;) SEG::a[dfn[i]]&＃61;w[i];for(int i&＃61;n&＃43;1;i<&＃61;all;i&＃43;&＃43;){for(int j&＃61;head[i];j;j&＃61;e[j].next){int y&＃61;e[j].ver;if (y!&＃61;fa[i]) SM[i].insert(w[y]);}if(SM[i].empty()) w[i]&＃61;1e9;else w[i]&＃61;*SM[i].begin();SEG::a[dfn[i]]&＃61;w[i];}SEG::bulid(1,1,all);}void add1(int x,int num){int f&＃61;fa[x];if(f){SM[f].erase(SM[f].find(w[x]));SM[f].insert(num);w[f]&＃61;*SM[f].begin();SEG::update(1,1,all,dfn[f],w[f]);}w[x]&＃61;num;SEG::update(1,1,all,dfn[x],num);}int ask(int x,int y){int ans&＃61;1e9;while(top[x]!&＃61;top[y]){if(d[top[x]]<d[top[y]]) swap(x,y);ans&＃61;min(ans,SEG::ask(1,1,all,dfn[top[x]],dfn[x]));x&＃61;fa[top[x]];}if(d[x]>d[y]) swap(x,y);ans&＃61;min(ans,SEG::ask(1,1,all,dfn[x],dfn[y]));if(x>n) ans&＃61;min(ans,w[fa[x]]);// return ans;}
}
namespace GP1
{struct node{int ver,next;}e[N];int tot&＃61;1,head[N];int dfn[N],low[N];int num,instack[N],top,sum;void add(int x,int y){e[&＃43;&＃43;tot].ver&＃61;y;e[tot].next&＃61;head[x];head[x]&＃61;tot;}void addedge(int x,int y){add(x,y);add(y,x);}void tarjan(int x,int in_edge){dfn[x]&＃61;low[x]&＃61;&＃43;&＃43;sum;instack[&＃43;&＃43;top]&＃61;x;
// cout<for(re i&＃61;head[x];i;i&＃61;e[i].next){int y&＃61;e[i].ver;if(!dfn[y]){tarjan(y,i);low[x]&＃61;min(low[x],low[y]);if(low[y]>&＃61;dfn[x]){all&＃43;&＃43;;w[all]&＃61;1e9;int z;do{z&＃61;instack[top--];GP2::addedge(z,all);}while(z!&＃61;y);GP2::addedge(x,all);w[all]&＃61;min(w[all],w[x]);}}else if(i!&＃61;(in_edge^1)) low[x]&＃61;min(low[x],dfn[y]);}}
}
void solve()
{cin>>n>>m>>q;all&＃61;n;for(re i&＃61;1;i<&＃61;n;i&＃43;&＃43;) scanf("%d",&w[i]);for(re i&＃61;1;i<&＃61;m;i&＃43;&＃43;){int x,y;scanf("%d%d",&x,&y);GP1::addedge(x,y);}GP1::tarjan(1,0);GP2::init();while(q--){char op[5];int x,y;scanf("%s%d%d",op,&x,&y);if(op[0]&＃61;&＃61;&＃39;C&＃39;) GP2::add1(x,y);else printf("%d\n",GP2::ask(x,y));}
}
signed main()
{
// fflush(stdout);
// srand(102321547);
// freopen("9.in.txt", "r", stdin);
// freopen("9.out.txt", "w", stdout);
// freopen("9.out", "w", stdout);int T&＃61;1;
// cin>>T;for(int index&＃61;1;index<&＃61;T;index&＃43;&＃43;){
// printf("Case %d: ",index);solve();
// puts("");}return 0;
}
/*
7 9 1
1
2
3
4
5
6
7
1 2
2 5
1 5
2 3
3 4
2 4
5 6
6 7
5 7
A 6 7*/