题目链接:这里
我的代码
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;
template<class T>
inline void read(T &x)
{
static char ch;
static bool opt;
while(!isdigit(ch=getchar())&&ch!='-');
x=(opt=ch=='-')?0:ch-'0';
while(isdigit(ch=getchar()))x=x*10+ch-'0';
if(opt)x=~x+1;
}
inline void tense(int &x,const int &y)
{
if(x>y)x=y;
}
const int MaxNV=2e4+5;
const int MaxNE=MaxNV<<1;
const int MaxNode=MaxNV<<2;
int n,m,ect,ans[MaxNV],adj[MaxNV],to[MaxNV],nxt[MaxNE],dep[MaxNV],fa[MaxNV],sze[MaxNV],son[MaxNV],seg[MaxNV],rev[MaxNV],top[MaxNV],totpos,sum[MaxNode],tag[MaxNode];
#define trav(u)for(int e=adj[u],v;v=to[e],e;e=nxt[e])
inline void addEdge(const int &u,const int &v)
{
nxt[++ect]=adj[u],adj[u]=ect,to[ect]=v;
nxt[++ect]=adj[v],adj[v]=ect,to[ect]=u;
}
inline void init()
{
ect=0;
memset(sum,0,sizeof(sum));
memset(tag,0,sizeof(tag));
memset(top,0,sizeof(top));
memset(son,0,sizeof(son));
memset(adj,0,sizeof(adj));
}
inline void dfs1(const int &u)
{
dep[u]=dep[fa[u]+1];
sze[u]=1;
trav(u)
{
if(v!=fa[u])
{
fa[v]=u;
dfs1(v);
sze[u]+=sze[v];
if(sze[v]>sze[son[u]])son[u]=v;
}
}
}
inline void dfs2(const int &u)
{
if(son[u])
{
rev[seg[son[u]]=++totpos]=son[u];
top[son[u]]=top[u];
dfs2(son[u]);
}
trav(u)
{
if(v!=fa[u]&&v!=son[u])
{
rev[seg[v]=++totpos]=v;
top[v]=v;
dfs2(v);
}
}
}
#define lc(x<<1)
#define rc(x<<1|1)
inline void upt(const int &x)
{
sum[x]=sum[lc]+sum[rc];
}
inline void add(const int &x,const int &l,const int &r,const int &v)
{
sum[x]+=v*(r-l+1);
tag[x]+=v;
}
inline void dnt(const int &x,const int &l,const int &r)
{
if(tag[x])
{
int mid=l+r>>1;
add(lc,l,mid,tag[x]);
add(rc,mid+1,t,tag[x]);
tag[x]=0;
}
}
inline void my(const int &x,const int &l,const int &r,const int &u,const int &v)
{
if(u<=l&&r<=v)return add(x,l,r,1);
dnt(x,l,r);
int mid=l+r>>1;
if(u<=mid)my(lc,l,mid,u,v);
if(v>mid)my(rc,mid+1,r,u,v);
upt(x);
}
inline int qq(const int &x,const int &l,const int &t,const int &p)
{
if(l==r)return sum[x];
dnt(x,l,r);
int mid=l+r>>1;
if(p<=mid)return qq(lc,l,mid,p);
else return qq(rc,mid+1,r,p);
}
inline void pm(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])std::swap(u,v);
my(1,1,n,seg[top[u]],seg[u]);
u=fa[top[u]];
}
if(dep[u]>=dep[v])std::swap(u,v);
if(u!=v)my(1,1,n,seg[u]+1,seg[v]);
}
int main()
{
int T;
read(T);
while(T--)
{
read(n);read(m);
init();
for(int i=1,u,v;i<n;i++)
{
read(u),read(v);
addEdge(u,v);
}
dfs1(1);
seg[1]=rev[1]=top[1]=totpos=1;
dfs2(1);
int tmp=m-n+1;
for(int i=1,u,v;i<=tmp;i++)
{
read(u),read(v);
pm(u,v);
}
int ans=m+1;
for(int i=2;i<=n;i++)tense(ans,qq(1,1,n,seg[i]));
printf("%d\n",ans+1);
}
return 0;
}
编译错误了,哪位大佬帮改一下行不?