NOIP2016天天爱跑步解题思路

算法：LCA，树上差分+（乱搞）

如果有写错的地方请大佬更正

对于100%数据：

u表示起点，v表示终点

对于一条u到v的路径，先讨论LCA!=u&&LCA!=v的情况：

分为u到LCA的路径和LCA到v的路径

对于u到LCA的路径上的点x，当deep[u]-deep[x]=w[x]时，即w[x]+deep[x]=deep[u]时，这条路径对点x有贡献；

观察发现w[x]+deep[x]是定值，所以统计经过x的路径中，deep[u]=w[x]+deep[x]的路径条数。

对于LCA到v的路径上的点x，当deep[u]-2*deep[LCA]+deep[x]=w[x]时，即w[x]-deep[x]=deep[u]-2*deep[lca]时，这条路径对点x有贡献；

观察发现w[x]-deep[x]是定值，所以统计经过x的路径中，deep[u]-2*deep[lca]=w[x]-deep[x]的路径条数；

接下来就是统计路径条数了，用到树上差分

我们统计的起点(终点）一定在点x子树内，所以统计x子树内有多少起点（终点)的值等于所需值

即统计有多少个在点x子树内的起点的deep[u]的值与deep[x]+w[x]相同

有多少终点的deep[u]-2*deep[lca]与w[x]-deep[x]相同

对于一个值，再u、v上加一个表示这个值+1的标记

考虑到x子树内的路径不一定经过x，所以在father[LCA]上加一个标记表示这个值-1

标记用动态数组储存

然后一遍dfs用两个桶分别统计，统计时值统一加上n，因为可能出现负数

记录下dfs到父亲节点时自己（也就是父亲的儿子）所需值的个数，然后统计完子树的值之后再做差计算自己

对于LCA==u||LCA==v的情况归于以上两类计算，特殊处理一下

另外，对于分裂成两条链LCA可能会被统计两遍，最后特殊判断一下，如果被统计了两遍就减去一遍,

复杂度：

LCA O(mlogn）

dfs统计 O(n)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#define N 300009

using namespace std;

int n,m;

vector<int>G[N];

int W[N];

int S[N],T[N],LCA[N];

int father[N],son[N],depth[N];

int heavyson[N],top[N];

int dfs1(int now,int fa){

	father[now]=fa;

	son[now]=1;

	depth[now]=depth[fa]+1;

	for(int i=0;i<G[now].size();++i){

		if(G[now][i]!=fa){

			dfs1(G[now][i],now);

			son[now]+=son[G[now][i]];

			if(son[G[now][i]]>son[heavyson[now]])heavyson[now]=G[now][i];

		}

	}

}

int dfs2(int now,int first){

	top[now]=first;

	if(!heavyson[now])return 0;

	dfs2(heavyson[now],first);

	for(int i=0;i<G[now].size();++i){

		if(G[now][i]!=father[now]&&G[now][i]!=heavyson[now])dfs2(G[now][i],G[now][i]);

	}

}

int swap(int &a,int &b){

	int t=a;a=b;b=t;

}

int lca(int u,int v){

	int tu=top[u],tv=top[v];

	while(tu!=tv){

		if(depth[tu]<depth[tv]){

			swap(tu,tv);swap(u,v);

		}

		u=father[tu];tu=top[u];

	}

	if(depth[u]<depth[v])return u;

	else return v;

}

int cnt[N];

int T1[N+N],T2[N+N];

struct tag{

	int v,siz;

};

vector<tag>tag1[N];

vector<tag>tag2[N];

int dfs(int now,int a,int b){

	for(int i=0;i<tag1[now].size();++i){

		T1[tag1[now][i].v+N]+=tag1[now][i].siz;

	}

	for(int i=0;i<tag2[now].size();++i){

		T2[tag2[now][i].v+N]+=tag2[now][i].siz;

	}

	for(int i=0;i<G[now].size();++i){

		int v=G[now][i];

		if(v==father[now])continue;

		dfs(v,T1[W[v]+depth[v]+N],T2[W[v]-depth[v]+N]);

	}

	cnt[now]+=T1[W[now]+depth[now]+N]+T2[W[now]-depth[now]+N]-a-b;

}

int read(){

	int r=0,k=1;

	char c=getchar();

	for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;

	for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';

	return r*k;

}

int main(){

	n=read();m=read();

	for(int i=1;i<=n-1;++i){

		int x=read(),y=read();

		G[x].push_back(y);

		G[y].push_back(x);

	}

	for(int i=1;i<=n;++i)W[i]=read();

	for(int i=1;i<=m;++i)S[i]=read(),T[i]=read();

	dfs1(1,0),dfs2(1,1);

	for(int i=1;i<=m;++i)LCA[i]=lca(S[i],T[i]);

	for(int i=1;i<=m;++i){

		if(LCA[i]==T[i]){

			tag1[S[i]].push_back((tag){depth[S[i]],1});

			tag1[father[T[i]]].push_back((tag){depth[S[i]],-1});

		}else if(LCA[i]==S[i]){

			tag2[T[i]].push_back((tag){depth[S[i]]-2*depth[LCA[i]],1});

			tag2[father[S[i]]].push_back((tag){depth[S[i]]-2*depth[LCA[i]],-1});

		}else{

			if(W[LCA[i]]+depth[LCA[i]]==depth[S[i]])--cnt[LCA[i]];

			tag1[S[i]].push_back((tag){depth[S[i]],1});

			tag1[father[LCA[i]]].push_back((tag){depth[S[i]],-1});

			tag2[T[i]].push_back((tag){depth[S[i]]-2*depth[LCA[i]],1});

			tag2[father[LCA[i]]].push_back((tag){depth[S[i]]-2*depth[LCA[i]],-1});

		}

	}

	dfs(1,0,0);

	for(int i=1;i<=n;++i)printf("%d ",cnt[i]);

	return 0;

}

巴特西

NOIP2016天天爱跑步解题思路

最新文章

热门文章