# Hdu4582 dfs spanning tree

## 花式树上贪心乱搞

Posted by yjjr's blog on March 11, 2019

# Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<bitset>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg1(x) for(int i=last[x];i;i=e[i].next)
#define reg2(x) for(int i=pre[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=2e3+6;
int pre[maxn<<2],last[maxn<<2],cnt=0,ans,n,m;
bool vis[maxn];
struct edge{int to,next;}e[maxn<<5];
bitset<maxn> To[maxn];
void insert1(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;}
void insert2(int u,int v){e[++cnt]=(edge){v,pre[u]};pre[u]=cnt;}
void dfs(int x,int fa){
vis[x]=1;
To[x].reset();
reg2(x)if(vis[e[i].to])To[x].set(e[i].to);
reg1(x){if(e[i].to==fa)continue;dfs(e[i].to,x);}
//cout<<x<<' '<<fa<<"R"<<endl;
if(fa==0)return;
if(To[x].test(fa))ans++;else To[fa]|=To[x];
}
int main(){
while(n&&m){
mem(last,0);mem(pre,0);cnt=0;mem(e,0);mem(vis,0);
rep(i,1,n-1){
insert1(u,v);insert1(v,u);
}
rep(i,n,m){