这个权值\(\le 2^{31}\)好诡异呀。。不过没有\(2^{31}\)出现还算良心
直接令某个点为根树剖，查询时分情况讨论：
被查询点就是根：直接查询所有点
根在被查询点的子树中：找到根在被查询点哪个儿子的子树中，查询除了那个儿子的子树的部分
其他情况：直接查询被查询点的子树
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
// <3083.cpp> - Fri Mar 10 16:45:31 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; #define next NEXT #define end END template<typename T> inline void gg(T &res){ res=0;T fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); res*=fh; } inline int gi(){int x;gg(x);return x;} inline lol gl(){lol x;gg(x);return x;} const int MAXN=100010; const int MAXM=200010; const int MAXK=MAXN<<2; const int INF=2147483647; int bt,b[MAXN],next[MAXM],to[MAXM]; inline void add(int x,int y){ next[++bt]=b[x];b[x]=bt;to[bt]=y; next[++bt]=b[y];b[y]=bt;to[bt]=x; } int f[MAXN],dep[MAXN],size[MAXN],s[MAXN]; void dfs1(int x){ size[x]=1; for(int i=b[x];i;i=next[i]){ if(to[i]==f[x])continue; f[to[i]]=x; dep[to[i]]=dep[x]+1; dfs1(to[i]); size[x]+=size[to[i]]; if(size[to[i]]>size[s[x]])s[x]=to[i]; } } int dt,dfn[MAXN],end[MAXN],top[MAXN]; void dfs2(int x,int t){ dfn[x]=++dt;top[x]=t; if(s[x])dfs2(s[x],t); for(int i=b[x];i;i=next[i]) if(to[i]!=f[x]&&to[i]!=s[x])dfs2(to[i],to[i]); end[x]=dt; } int n,a[MAXN],val[MAXK],lazy[MAXK]; inline void update(int x){val[x]=min(val[x<<1],val[x<<1|1]);} void build(int x,int l,int r){ if(l==r){val[x]=a[l];return;} int m=l+r>>1; build(x<<1,l,m); build(x<<1|1,m+1,r); update(x); } inline void pushdown(int x){ if(!lazy[x])return; val[x<<1]=val[x<<1|1]=lazy[x<<1]=lazy[x<<1|1]=lazy[x]; lazy[x]=0; } void mod(int v,int L,int R,int l=1,int r=n,int x=1){ if(l==L&&r==R){val[x]=lazy[x]=v;return;} pushdown(x); int m=l+r>>1; if(L<=m)mod(v,L,min(R,m),l,m,x<<1); if(R>m)mod(v,max(L,m+1),R,m+1,r,x<<1|1); update(x); } int ask(int L,int R,int l=1,int r=n,int x=1){ if(L>R)return INF; if(l==L&&r==R)return val[x]; pushdown(x); int m=l+r>>1,ans=INF; if(L<=m)ans=min(ans,ask(L,min(R,m),l,m,x<<1)); if(R>m)ans=min(ans,ask(max(L,m+1),R,m+1,r,x<<1|1)); return ans; } int main(){ n=gi();int m=gi(); for(int i=1;i<n;i++)add(gi(),gi()); dfs1(1);dfs2(1,1); for(int i=1;i<=n;i++)a[dfn[i]]=gi(); build(1,1,n); int rt=gi(); while(m--){ int op=gi(); if(op==1)rt=gi(); else if(op==2){ int x=gi(),y=gi(),z=gi(); while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); mod(z,dfn[top[x]],dfn[x]); x=f[top[x]]; } if(dep[x]<dep[y])swap(x,y); mod(z,dfn[y],dfn[x]); }else{ int x=gi(); if(x==rt)printf("%d\n",ask(1,n)); else if(dfn[x]<=dfn[rt]&&dfn[rt]<=end[x]){ int p=rt; if(dfn[s[x]]<=dfn[rt]&&dfn[rt]<=end[s[x]])p=s[x]; else while(f[p]!=x)p=top[f[p]]; printf("%d\n",min(ask(1,dfn[p]-1),ask(end[p]+1,n))); }else printf("%d\n",ask(dfn[x],end[x])); } } return 0; } |
话说2^31开个unsigned int不就好了
懒得开