这题真是神题！
当然我不是说这题有多神，而是你数组开小了和开大了得分不同，用不同版本的编译器得分不同。。。（数组没有越界的情况下）
呜呜。。。至今没有ac。一直83分。。。抑郁了。。。
跪求神犇指明错误。。。
View Code
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 #include <cstdio> 6 7 #define N 151000 8 #define M 251000 9 #define INF 1e9 10 11 using namespace std; 12 13 struct RT 14 { 15 int mn,zb; 16 }rt[N<<2]; 17 18 int head[N],to[M],next[M]; 19 int tot,n,qu,cnt; 20 int fa[N],son[N],sz[N],dep[N],top[N],q[N]; 21 int bh[N],anbh[N]; 22 23 inline void add(int u,int v) 24 { 25 to[cnt]=v; next[cnt]=head[u]; head[u]=cnt++; 26 } 27 28 inline void init() 29 { 30 memset(head,-1,sizeof head); cnt=0; 31 tot=0; 32 } 33 34 inline void prep() 35 { 36 int h=1,t=2,sta; 37 q[1]=1; dep[1]=1; 38 while(h<t) 39 { 40 sta=q[h++]; sz[sta]=1; 41 for(int i=head[sta];~i;i=next[i]) 42 if(to[i]!=fa[sta]) 43 { 44 fa[to[i]]=sta; 45 dep[to[i]]=dep[sta]+1; 46 q[t++]=to[i]; 47 } 48 } 49 for(int j=t-1;j>=1;j--) 50 { 51 sta=q[j]; 52 for(int i=head[sta];~i;i=next[i]) 53 if(to[i]!=fa[sta]) 54 { 55 sz[sta]+=sz[to[i]]; 56 if(sz[to[i]]>sz[son[sta]]) son[sta]=to[i]; 57 } 58 } 59 for(int i=1;i<t;i++) 60 { 61 sta=q[i]; 62 if(son[fa[sta]]==sta) top[sta]=top[fa[sta]]; 63 else top[sta]=sta; 64 } 65 } 66 67 inline void rewrite() 68 { 69 for(int i=1;i<=n;i++) 70 if(top[i]==i) 71 for(int j=i;j;j=son[j]) 72 { 73 bh[j]=++tot; 74 anbh[tot]=j; 75 } 76 } 77 78 inline void pushup(int u) 79 { 80 if(rt[u<<1].mn<rt[u<<1|1].mn) rt[u]=rt[u<<1]; 81 else rt[u]=rt[u<<1|1]; 82 } 83 84 inline void build(int u,int L,int R) 85 { 86 if(L==R) {rt[u].mn=INF;rt[u].zb=L;return;} 87 int MID=(L+R)>>1; 88 build(u<<1,L,MID); build(u<<1|1,MID+1,R); 89 pushup(u); 90 } 91 92 inline void read() 93 { 94 init(); 95 scanf("%d%d",&n,&qu); 96 for(int i=1,a,b;i<n;i++) 97 { 98 scanf("%d%d",&a,&b); 99 add(a,b); add(b,a); 100 } 101 prep(); 102 rewrite(); 103 build(1,1,tot); 104 } 105 106 inline int queryval(int u,int L,int R,int pos) 107 { 108 if(L==R) return rt[u].mn; 109 int MID=(L+R)>>1; 110 if(pos<=MID) return queryval(u<<1,L,MID,pos); 111 return queryval(u<<1|1,MID+1,R,pos); 112 } 113 114 inline void updata(int u,int L,int R,int pos,int val) 115 { 116 if(L==R) {rt[u].mn=val;return;} 117 int MID=(L+R)>>1; 118 if(pos<=MID) updata(u<<1,L,MID,pos,val); 119 else updata(u<<1|1,MID+1,R,pos,val); 120 pushup(u); 121 } 122 123 inline void change(int x) 124 { 125 int val=queryval(1,1,tot,bh[x]); 126 if(val==INF) updata(1,1,tot,bh[x],dep[x]); 127 else updata(1,1,tot,bh[x],INF); 128 } 129 130 inline RT querymin(int u,int L,int R,int l,int r) 131 { 132 if(l<=L&&R<=r) return rt[u]; 133 int MID=(L+R)>>1; RT lp,rp; lp.mn=rp.mn=INF; 134 if(l<=MID) lp=querymin(u<<1,L,MID,l,r); 135 if(MID<r) rp=querymin(u<<1|1,MID+1,R,l,r); 136 if(lp.mn<rp.mn) return lp; 137 return rp; 138 } 139 140 inline void query(int x,int y) 141 { 142 RT tmp,res; res.mn=INF; 143 while(top[x]!=top[y]) 144 { 145 if(dep[top[x]]<dep[top[y]]) swap(x,y); 146 tmp=querymin(1,1,tot,bh[top[x]],bh[x]); 147 if(tmp.mn<res.mn) res=tmp; 148 x=fa[top[x]]; 149 } 150 if(bh[x]>bh[y]) swap(x,y); 151 tmp=querymin(1,1,tot,bh[x],bh[y]); 152 if(tmp.mn<res.mn) res=tmp; 153 if(res.mn!=INF) printf("%d\n",anbh[res.zb]); 154 else puts("-1"); 155 } 156 157 inline void go() 158 { 159 int a,b; 160 while(qu--) 161 { 162 scanf("%d%d",&a,&b); 163 if(a==0) change(b); 164 else query(b,1); 165 } 166 } 167 168 int main() 169 { 170 read(),go(); 171 return 0; 172 }