求助一道站外题
  • 板块学术版
  • 楼主清风雪月
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/3/6 16:26
  • 上次更新2023/10/28 07:08:18
查看原帖
求助一道站外题
388857
清风雪月楼主2022/3/6 16:26

题目链接:这里
我的代码

#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;
}

编译错误了,哪位大佬帮改一下行不?

2022/3/6 16:26
加载中...