2015 멀티 스쿨 1차전 1006 hdu 5293 Tree chain 문제

제목: 나무 한 그루를 정한 다음에 체인을 정하고 체인을 나무 위의 어떤 경로에 놓으면 모든 체인이 가치가 있고 체인을 취해야 한다. 그리고 얻은 체인이 교차하지 않아 얻은 체인의 총 가치가 가장 크다.
방법: 나무에 동적 계획을 하고 dp[i]를 열면 i번째 점이 뿌리인 자수 안의 체인의 최대 가치를 나타내고sum[i]는 i의 아들 노드의 dp가 화합할 가치가 있음을 나타낸다.체인을 고려할 때 체인의 경로에 있는 모든sum[i]-dp[i]를 합치면 (lca 그 점은sum[i]만 넣으면 된다) 이 체인의 가치를 합치면 이 체인의 가치를 찾아내고 다른 체인의 높이가 그 체인의 최대 가치보다 낮을 때 dp[lca]에 업데이트하는 것이 목적이다.그리고sum값으로 dp값을 업데이트하면 됩니다.깊이가 깊은 점에서 깊이가 얕은 점까지 한 번에 훑어본 다음에lca가 있는 체인을 찾으면 이동할 수 있다.
전체 시간의 복잡도는 o(nlognlogn)이고 처음에 라인 트리를 사용했을 때 본 컴퓨터는 2900ms로 hdu를 건네주면 tle가 된다.나중에 나무형 수조로 바뀌었습니다. 본기는 2900ms,hdu2300msac입니다.

 #pragma comment(linker, "/STACK:1024000000,1024000000") 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 101010
struct chain{
	int u,v;
	int w;
	int lca;
}cn[N];
/*********       *********/
int fa[N];
long long sum[N];
int que[N*2],ta,he;
/************    ************/
struct EDGE{
	int to,next;
}e[N*2];
int head[N],tot;
void addEDGE(int u,int v)
{
	e[tot].to=v;
	e[tot].next=head[u];
	head[u]=tot++;
}
/***********     ***********/
int f[N];
int find(int x)
{
	if(x!=f[x])f[x]=find(f[x]);
	return f[x];
}
/**********lca  ***************/
struct query{
	int Id,next;
}qu[N*2];
int qhead[N],qtot;
void addquery(int u,int Id)
{
	qu[qtot].Id=Id;
	qu[qtot].next=qhead[u];
	qhead[u]=qtot++;
}
void get_lca(int u)
{
	for(int i=qhead[u];i>=0;i=qu[i].next)
	{
		int Id=qu[i].Id;
		if(cn[Id].lca==-1)
		{
			cn[Id].lca=u;
		}
		else{
			cn[Id].lca=find(cn[Id].lca);
		}
	}
	int fu=find(u);
	for(int i=head[u];i>=0;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa[u])continue;
		fa[v]=u;
		get_lca(v);
		int fv=find(v);
		f[fv]=fu;
	}
}
/*****        **********/
struct node{
	long long sum,dpsum;
}stn[N];
node operator +(const node &a,const node &b)
{
	node c;
	c.sum=a.sum+b.sum;
	c.dpsum=a.dpsum+b.dpsum;
	return c;
}
node operator -(const node &a,const node &b)
{
	node c;
	c.sum=a.sum-b.sum;
	c.dpsum=a.dpsum-b.dpsum;
	return c;
}
int n,m;
int lowbit(int x)
{
	return x&(-x);
}
void update(int x,node val)
{
	while(x<=n)
	{
		stn[x]=stn[x]+val;
		x+=lowbit(x);
	}
}
node querys(int x)
{
	node c;
	c.sum=c.dpsum=0;
	while(x>0)
	{
		c=c+stn[x];
		x-=lowbit(x);
	}
	return c;
}
node queryS(int x,int y)
{
	if(y==1)return querys(x);
	else return querys(x)-querys(y-1);
}
/**********    **************/
int siz[N],son[N],top[N],nam[N],namtot,dep[N];
void dfs1(int u)
{
	siz[u]=1;
	son[u]=0;
	int k=0;
	for(int i=head[u];i>=0;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa[u])continue;
		dep[v]=dep[u]+1;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>k)
		{
			k=siz[v];
			son[u]=v;
		}
	}
}
void dfs2(int u,int tp)
{
	top[u]=tp;
	nam[u]=namtot++;
	if(son[u])dfs2(son[u],tp);
	for(int i=head[u];i>=0;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}

/********************************/

void INIT(int n)
{
	namtot=1;
	tot=qtot=0;
	for(int i=1;i<=n;i++)
	{
		stn[i].sum=stn[i].dpsum=0;
		f[i]=i;
		head[i]=qhead[i]=-1;
		sum[i]=0;
	}
}
long long Query(chain a,long long s,long long w)
{
	int u=a.u;
	int v=a.v;
	int lca=a.lca;
	int as=s+w;
	node st;
	while(1)
	{
		if(top[u]!=top[lca])
		{
			st=queryS(nam[u],nam[top[u]]);
			as+=st.sum-st.dpsum;
		}
		else {
			st=queryS(nam[u],nam[lca]);
			as+=st.sum-st.dpsum;
			break;
		}
		u=fa[top[u]];
	}
	while(v!=lca)
	{
		if(top[v]!=top[lca])
		{
			st=queryS(nam[v],nam[top[v]]);
			as+=st.sum-st.dpsum;
		}
		else
		{
			st=queryS(nam[v],nam[lca]+1);
			as+=st.sum-st.dpsum;
			break;
		} 
		v=fa[top[v]];
	}
	return as;
}
int main()
{
//	clock_t stime=clock();
//	freopen("1006.in","r",stdin);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		
		scanf("%d%d",&n,&m);
		INIT(n);
		for(int i=1;i=0;i=e[i].next)
			{
				int v=e[i].to;
				if(v!=fa[u])que[ta++]=v;
			}
		}
		for(int i=ta-1;i>=0;i--)
		{
			int u=que[i];
			long long dps=0;
			for(int j=qhead[u];j>=0;j=qu[j].next)
			{
				dps=max(dps,Query(cn[qu[j].Id],sum[u],cn[qu[j].Id].w));
			}
			if(dps