2019.7.9 义乌模拟赛 T4 D

本文主要是介绍2019.7.9 义乌模拟赛 T4 D，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

我真是tcl居然没有调出来。
首先套路地拆成上行和下行两端。
先考虑上行，对于一个点\(u\)如果满足条件那么它一定满足\(d_l-d_{u}=u\)
移项得到\(d_l=d_u+u\)
这不是链上数一个数的个数吗，dfs的时候差分询问开桶记录即可。
然后下行也是一样的。
总的时间复杂度\(O(mlogn+n)\)时间复杂度瓶颈在lca上。
code:

#include<bits/stdc++.h>
#include<set>
#define ll long long
#define re register
#define I inline
#define N 300000
#define M 100
#define W 100000
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define Me(x,y) memset(x,y,sizeof(x))
#define it iterator
#define Gc() getchar()
using namespace std;
int n,m,xs,ys,x[N+5],y[N+5],z[N+5],fa[N+5],d[N+5],top[N+5],siz[N+5],son[N+5],Ans[N+5],F[N+5<<1];
struct yyy{int to,z;};
struct ljb{
	int head,h[N+5];yyy f[N+5<<1];
	I void add(int x,int y){f[++head]=(yyy){y,h[x]};h[x]=head;}
}s;
struct ques{int id,x,flag;}now;vector<ques> Q[N+5];
I void dfs1(int x,int last){
	d[x]=d[last]+1;siz[x]=1;fa[x]=last;yyy tmp;for(int i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^last&&(dfs1(tmp.to,x),siz[x]+=siz[tmp.to],siz[tmp.to]>siz[son[x]]&&(son[x]=tmp.to));
}
I void dfs2(int x,int last){
	top[x]=last;if(!son[x]) return;yyy tmp;dfs2(son[x],last);for(int i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^fa[x]&&tmp.to^son[x]&&(dfs2(tmp.to,tmp.to),0);
}
I int lca(int x,int y){while(top[x]^top[y]) d[top[x]]>d[top[y]]?(x=fa[top[x]]):y=(fa[top[y]]);return d[x]>d[y]?y:x;}
I void GetAns1(int x){
	F[d[x]+x]++;int i;yyy tmp;for(i=0;i<Q[x].size();i++) now=Q[x][i],Ans[now.id]+=F[now.x]*now.flag;
	for(i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^fa[x]&&(GetAns1(tmp.to),0);F[d[x]+x]--;
}
I void GetAns2(int x){
	F[x-d[x]+n]++;int i;yyy tmp;for(i=0;i<Q[x].size();i++) now=Q[x][i],Ans[now.id]+=F[now.x+n]*now.flag;
	for(i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^fa[x]&&(GetAns2(tmp.to),0);F[x-d[x]+n]--;
}
I void read(int &x){
	char s=getchar();x=0;while(s<'0'||s>'9') s=Gc();
	while(s>='0'&&s<='9') x=x*10+s-48,s=Gc();
}
int main(){
	freopen("d.in","r",stdin);freopen("d.out","w",stdout);
	re int i,j;scanf("%d%d",&n,&m);for(i=1;i<n;i++) read(xs),read(ys),s.add(xs,ys),s.add(ys,xs);dfs1(1,0);dfs2(1,1);
	for(i=1;i<=m;i++) read(x[i]),read(y[i]),z[i]=lca(x[i],y[i]),Q[x[i]].push_back((ques){i,d[x[i]],1}),Q[fa[z[i]]].push_back((ques){i,d[x[i]],-1});GetAns1(1);
	for(i=1;i<=n;i++) Q[i].clear();for(i=1;i<=m;i++) Q[y[i]].push_back((ques){i,d[x[i]]-2*d[z[i]],1}),Q[z[i]].push_back((ques){i,d[x[i]]-2*d[z[i]],-1});GetAns2(1);
	for(i=1;i<=m;i++) printf("%d\n",Ans[i]);
}

这篇关于2019.7.9 义乌模拟赛 T4 D的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！