BZOJ 3611 HEOI2014 大工程 倍增LCA+單調棧+樹形DP

BZOJ 3611 HEOI2014 大工程 倍增LCA+單調棧+樹形DP

題目大意：給定一棵樹，m次詢問，每次給出k個關鍵點，詢問這k個點之間的兩兩距離和、最小距離和最大距離

n<=100W,m<=50000,Σk<=2*n

處理方法同2286 消耗戰 地址見 www.Bkjia.com

這個題的DP有些麻煩 因此我把要處理的節點單獨拎出來做的DP 具體狀態和轉移見代碼

#include 
#include 
#include 
#include 
#define M 1001001
#define INF 0x3f3f3f3f
using namespace std;
struct abcd{
	int to,next;
}table[M<<1];
int head[M],tot;
int n,m;
int pos[M],dpt[M],fa[M][20];
long long ans,ans_min,ans_max;
bool is_key_point[M];
void Add(int x,int y)
{
	table[++tot].to=y;
	table[tot].next=head[x];
	head[x]=tot;
}
void DFS(int x)
{
	static int cnt=0;
	int i;
	pos[x]=++cnt;dpt[x]=dpt[fa[x][0]]+1;
	for(i=head[x];i;i=table[i].next)
		if(table[i].to!=fa[x][0])
		{
			fa[table[i].to][0]=x;
			DFS(table[i].to);
		}
}
int LCA(int x,int y)
{
	int j;
	if(dpt[x]=dpt[y])
			x=fa[x][j];
	if(x==y) return x;
	for(j=19;~j;j--)
		if(fa[x][j]!=fa[y][j])
			x=fa[x][j],y=fa[y][j];
	return fa[x][0];
}
bool Compare(int x,int y)
{
	return pos[x] < pos[y] ;
}
void Tree_DP(int x,int from)
{
	static long long f[M],g[M],max_dis[M],min_dis[M];
	//f[x]表示以x為根的子樹中有多少關鍵點
	//g[x]表示以x為根的子樹中所有關鍵點到x的距離之和
	//max_dis[x]/min_dis[x]表示節點x為根的子樹中的關鍵點到x的距離的最大/最小值
	int i;
	f[x]=is_key_point[x];g[x]=0;
	max_dis[x]=(is_key_point[x]?0:-INF);
	min_dis[x]=(is_key_point[x]?0:INF);
	for(i=head[x];i;i=table[i].next)
	{
		if(table[i].to==from)
			continue;
		Tree_DP(table[i].to,x);
		int dis=dpt[table[i].to]-dpt[x];
		ans+=(g[x]+f[x]*dis)*f[table[i].to]+g[table[i].to]*f[x];
		ans_min=min(ans_min,min_dis[x]+min_dis[table[i].to]+dis);
		ans_max=max(ans_max,max_dis[x]+max_dis[table[i].to]+dis);
		f[x]+=f[table[i].to];
		g[x]+=g[table[i].to]+f[table[i].to]*dis;
		max_dis[x]=max(max_dis[x],max_dis[table[i].to]+dis);
		min_dis[x]=min(min_dis[x],min_dis[table[i].to]+dis);
	}
}
int main()
{
	int i,j,k,x,y;
	cin>>n;
	for(i=1;i>m;
	for(i=1;i<=m;i++)
	{
		static int a[M];
		static int stack[M],top;
		scanf(%d,&k);
		for(j=1;j<=k;j++)
			scanf(%d,&a[j]);
		sort(a+1,a+k+1,Compare);
		tot=0;
		stack[top=1]=1;
		head[1]=0;is_key_point[1]=(a[1]==1);
		for(j=1;j<=k;j++)
		{
			int lca=LCA(a[j],stack[top]);
			while(dpt[lca]1)
			Add(stack[top-1],stack[top]),top--;
		ans=0;ans_min=INF;ans_max=-INF;
		Tree_DP(1,0);
		#ifdef ONLINE_JUDGE
			printf(%lld %lld %lld
,ans,ans_min,ans_max);
		#else
			printf(%I64d %I64d %I64d
,ans,ans_min,ans_max);
		#endif
	}
	return 0;
}