蒟蒻求助 48分;2~7,14&15 WA;TarjanLCA+树上差分
查看原帖
蒟蒻求助 48分;2~7,14&15 WA;TarjanLCA+树上差分
137105
ShiLuohe楼主2020/9/9 16:41
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;

int n,m,s=1;
int st[100010],ed[100010];

//LCA部分 
//树 
struct edge
{
	int to,next,w;
} edge[100010],req[200010];
int head[50010],tot=1;
void add(int u,int v)
{
	edge[tot].to=v;
	edge[tot].next=head[u];head[u]=tot++;
}
//LCA请求关系图 
int reqh[50010],reqt=1;
void addreq(int u,int v,int w)
{
	req[reqt].to=v;req[reqt].w=w;
	req[reqt].next=reqh[u];reqh[u]=reqt++;
}
//并查集 
int f[50010];
int find(int x)
{
	if(f[x]==x) return x;
	else return f[x]=find(f[x]);
}
void init(int maxn)
{
	for(int i=0;i<=maxn;i++)
	    f[i]=i;
}
//Tarjan 
bool vis[50010];
int ans[50010];
void dfs(int u)
{
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(vis[v]) continue;
		vis[v]=1;
		dfs(v);
		f[find(v)]=find(u);
	}
	for(int i=reqh[u];i;i=req[i].next)
	{
		int v=req[i].to;
		if(!vis[v]) continue;
		ans[req[i].w]=find(v);
	}
}
//树上差分
//初始化父亲数组 
int fa[50010],val[50010];
void init2(int u)
{
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(fa[v]) continue; 
		fa[v]=u;
		init2(v);
	}
}
//获取每个点最终的权值 
int ansn=0;
int getans(int u,int fa)
{
	int ret=val[u];
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue; 
		ret+=getans(v,u);
	}
	ansn=max(ansn,ret);
	return ret;
}

int main()
{
	//freopen("P3128_2.in","r",stdin);
	scanf("%d%d",&n,&m);
	//建图*2 
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&st[i],&ed[i]);
		addreq(st[i],ed[i],i);addreq(ed[i],st[i],i);
	}
	//初始化差分 
	fa[s]=n+1;
	init2(s);
	//求LCA 
	init(n);
	vis[s]=1;
	dfs(s);
	//依据请求及其LCA维护差分 
	for(int i=1;i<=m;i++)
	{
		val[st[i]]++;val[ed[i]]++;
		val[ans[i]]--;val[fa[ans[i]]]--;
	}
	getans(s,n+1);
	printf("%d\n",ansn);
	return 0;
}
2020/9/9 16:41
加载中...