链接

　　http://www.lydsy.com/JudgeOnline/problem.php?id=3306

题解

　　mdzz我把maxk写成了maxn，不TLE才怪呢，随机数据死活拍不出错。 　　看来以后做树的题目应该把链、菊花图、扫把图都造一遍。 　　可以自行 YY 下 dfs 序+线段树。 　　 popoqqq 大爷就是强，用了 stl+lct ，我虽然也能口胡但是绝对不敢写…

代码

//线段树+dfs序 #include <cstdio> #include <algorithm> #include <cmath> #define maxn 200010 #define maxk 18 using namespace std; int N, head[maxn], to[maxn], w[maxn], nex[maxn], tid[maxn], val[maxn], tmp[maxn], deep[maxn], R, tot, f[maxn][maxk], ndtot, Q, out[maxn]; struct segtree{int l, r, min;segtree *ch[2];}pool[maxn], *root; void segchg(segtree *p, int pos, int v) { int mid=p->l+p->r>>1; if(p->l==p->r){p->min=v;return;} if(pos<=mid)segchg(p->ch[0],pos,v); else segchg(p->ch[1],pos,v); p->min=min(p->ch[0]->min,p->ch[1]->min); } int segmin(segtree *p, int l, int r) { int mid=p->l+p->r>>1, ans=0x7fffffff; if(l<=p->l and r>=p->r)return p->min; if(l<=mid)ans=min(ans,segmin(p->ch[0],l,r)); if(r>mid)ans=min(ans,segmin(p->ch[1],l,r)); return ans; } void build(segtree *p, int l, int r) { int mid=l+r>>1; p->l=l, p->r=r; if(l==r){p->min=tmp[l];return;} build(p->ch[0]=pool+ ++ndtot,l,mid); build(p->ch[1]=pool+ ++ndtot,mid+1,r); p->min=min(p->ch[0]->min,p->ch[1]->min); } inline int read(int x=0) { char c=getchar(); while(c<48 or c>57)c=getchar(); while(c>=48 and c<=57)x=(x<<1)+(x<<3)+c-48, c=getchar(); return x; } inline void adde(int a, int b){to[++tot]=b;nex[tot]=head[a];head[a]=tot;} void dfs(int pos, int pre) { int p; deep[pos]=deep[pre]+1; tid[pos]=++*tid; tmp[*tid]=val[pos]; for(p=head[pos];p;p=nex[p])dfs(to[p],pos); out[pos]=*tid; } void init() { int i, k; N=read(); Q=read(); for(i=1;i<=N;i++)f[i][0]=read(), val[i]=read(), adde(f[i][0],i); dfs(1,0); for(k=1;k<maxk;k++)for(i=1;i<=N;i++)f[i][k]=f[f[i][k-1]][k-1]; build(root=pool+ ++ndtot,1,N); } int lca(int x, int y) { int k; if(deep[x]>deep[y])swap(x,y); for(k=maxk-1;k>=0;k--)if(deep[f[y][k]]>=deep[x])y=f[y][k]; if(x==y)return x; for(k=maxk-1;k>=0;k--)if(f[x][k]^f[y][k])x=f[x][k],y=f[y][k]; return f[x][0]; } int quiry(int pos) { int tmp; int L, wh, ans=0x7fffffff, k; if(pos==R)return segmin(root,1,N); L=lca(R,pos); if(L!=pos)return segmin(root,tid[pos],out[pos]); wh=R; for(k=maxk-1;k>=0;k--)if(deep[f[wh][k]]>deep[pos])wh=f[wh][k]; ans=segmin(root,1,tid[wh]-1); if(out[wh]<N)ans=min(ans,segmin(root,out[wh]+1,N)); return ans; } int main() { char type[2]; int i, x, y; init(); for(i=1;i<=Q;i++) { scanf("%s",type); if(*type=='V') x=read(), y=read(), segchg(root,tid[x],y); else if(*type=='E')R=read(); else printf("%d\n",quiry(read())); } return 0; }