|
暴力大法好！！！！！
纯暴力修改+查询。
此题数据卡所有正解，就是不卡暴力（经测试，在每点1s下，几乎所有正解都T了）
暴力压正解。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#define N 1000005
using namespace std;
int e=1,head[N];
struct edge{
int u,v,next;
}ed[2*N];
void add(int u,int v){
ed[e].u=u; ed[e].v=v;
ed[e].next=head[u]; head[u]=e++;
}
int fa[N],dep[N],id[N];
bool bo[N];
void dfs1(int x,int f,int d){
fa[x]=f; dep[x]=d;
for(int i=head[x];i;i=ed[i].next){
int v=ed[i].v;
if(v==f) continue;
id[v]=(i+1)/2;
dfs1(v,x,d+1);
}
}
void col(int x,int y){
if(dep[x]>dep[y]) swap(x,y);
while(dep[y]>dep[x]){
bo[id[y]]=1;
y=fa[y];
}
if(x==y) return;
while(x!=y){
bo[id[x]]=1; x=fa[x];
bo[id[y]]=1; y=fa[y];
}
return;
}
int pre(int x){
while(x!=1&&!bo[id[x]])
x=fa[x];
return x==1?0:id[x];
}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
int u,v;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs1(1,0,1);
int opt,x,y;
while(m--){
scanf("%d",&opt);
switch(opt){
case 1: scanf("%d",&x); printf("%d\n",pre(x)); break;
case 2: scanf("%d%d",&x,&y); col(x,y); break;
}
}
return 0;
}
| 
转播
