哪一题？
by Caden @ 2019-02-13 14:23:58
@[Caden](/space/show?uid=83807) P4092
by 加油！ @ 2019-02-13 14:25:24
emm...@[Inea](/space/show?uid=99716)
先看到dfs第二行的地方有个问题：where is `return`?
by Jelly_Goat @ 2019-02-13 14:26:49
懒得打字
贴代码
#include <cstdio>
const int MAXN=100010;
struct P {
bool ty;
int id,ans;
}p[MAXN];
int edv[MAXN<<1],ednxt[MAXN<<1];
int first[MAXN],cnt=0;
void add(int x,int y) {
edv[++cnt]=y;
ednxt[cnt]=first[x];
first[x]=cnt;
}
int col[MAXN];
char inp[3];
int ufs[MAXN];
int f[MAXN];
void dfs(int x,int fa) {
if(col[x]) ufs[x]=x;
else ufs[x]=fa;
f[x]=fa;
for(int i=first[x];i;i=ednxt[i])
{
int v=edv[i];
if(v==fa) continue;
dfs(v,x);
}
}
int find(int x) {
return x==ufs[x]x:ufs[x]=find(ufs[x]);
}
int main() {
int n,q;
scanf("%d%d",&n,&q);
int in1,in2;
for(int i=1;i<n;++i) {
scanf("%d%d",&in1,&in2);
add(in1,in2);
add(in2,in1);
}
col[1]=1;
for(int i=1;i<=q;++i) {
scanf("%s%d",inp,&p[i].id);
switch(inp[0]) {
case 'Q':{
p[i].ty=0;
break;
}
case 'C':{
p[i].ty=1;
++col[p[i].id];
break;
}
}
}
dfs(1,0);
f[1]=1;
for(int i=q;i>=1;--i) {
if(p[i].ty) {
--col[p[i].id];
if(!col[p[i].id])
ufs[p[i].id]=f[p[i].id];
} else {
p[i].ans=find(p[i].id);
}
}
for(int i=1;i<=q;++i) {
if(!p[i].ty) {
printf("%d\n",p[i].ans);
}
}
return 0;
}
by Caden @ 2019-02-13 14:32:13
希望更丰富的展现？使用Markdown
by Jelly_Goat @ 2019-02-13 14:40:58
确认是没救了...
我也这样做的（~~吸氧吧~~）
by Jelly_Goat @ 2019-02-13 14:44:12
@[Caden](/space/show?uid=83807) 抄题解代码有意思？
by meyi @ 2019-02-13 14:52:51
@[Jelly_Goat](/space/show?uid=122927)
dfs 的类型是 int 的
所以直接 return x 就好了
by _Grey @ 2019-02-13 15:56:08
@[Jelly_Goat](/space/show?uid=122927)
我这个代码吸氧也没有任何卵用
所以我在想最后一组数据是不是有问题
~~明明前十组都能A，最后一组怎么可能出问题~~
by _Grey @ 2019-02-13 16:16:47
啧
~~手动吸4级氧没用~~
最后一组数据~~专门卡朴素算法~~
@[Inea](/space/show?uid=99716)
by Jelly_Goat @ 2019-02-13 16:25:33