2.14

闲话

做题纪要

SP913 QTREE2 - Query on a tree II

• \(LCA\) 板子。

  点击查看代码

  struct node
  {
  	ll nxt,to,w;
  }e[20002];
  ll head[20002],dep[20002],dis[20002],fa[20002][25],N,cnt=0;
  void add(ll u,ll v,ll w)
  {
  	cnt++;
  	e[cnt].nxt=head[u];
  	e[cnt].to=v;
  	e[cnt].w=w;
  	head[u]=cnt;
  }
  void dfs(ll x,ll father,ll w)
  {
  	fa[x][0]=father;
  	dep[x]=dep[father]+1;
  	dis[x]=dis[father]+w;
  	for(ll i=1;(1<<i)<=dep[x];i++)
  	{
  		fa[x][i]=fa[fa[x][i-1]][i-1];
  	}
  	for(ll i=head[x];i!=0;i=e[i].nxt)
  	{
  		if(e[i].to!=father) 
  		{
  			dfs(e[i].to,x,e[i].w);
  		}
  	}
  }
  ll lca(ll x,ll y)
  {
  	if(dep[x]>dep[y])
  	{
  		swap(x,y);
  	}
  	for(ll i=N;i>=0;i--)
  	{
  		if(dep[x]+(1<<i)<=dep[y])
  		{
  			y=fa[y][i];
  		}			
  	}
  	if(x==y) 
  	{
  		return x;
  	}
  	else
  	{
  		for(ll i=N;i>=0;i--)
  		{
  			if(fa[x][i]!=fa[y][i])
  			{
  				x=fa[x][i];
  				y=fa[y][i];
  			}
  		}
  		return fa[x][0];
  	}
  }
  ll query_fa(ll x,ll y,ll k)
  {	
  	ll rt=lca(x,y);
  	if(dep[x]-dep[rt]+1<=k)
  	{
  		k=dep[y]-dep[rt]+1-(k-(dep[x]-dep[rt]+1));
  		swap(x,y);
  	}
  	for(ll i=N;i>=0;i--)
  	{
  		if((1<<i)+1<=k)
  		{
  			x=fa[x][i];
  			k-=(1<<i);
  		}
  	}
  	return x;
  }
  int main()
  {
  	ll t,n,u,v,w,k,i,j;
  	string pd;
  	cin>>t;
  	for(j=1;j<=t;j++)
  	{
  		cin>>n;
  		N=log2(n)+1;
  		cnt=0;
  		memset(e,0,sizeof(e));
  		memset(head,0,sizeof(head));
  		memset(dep,0,sizeof(dep));
  		memset(dis,0,sizeof(dis));
  		memset(fa,0,sizeof(fa));
  		for(i=1;i<=n-1;i++)
  		{
  			cin>>u>>v>>w;
  			add(u,v,w);
  			add(v,u,w);
  		}
  		dfs(1,0,0);
  		while(cin>>pd)
  		{
  			if(pd=="DONE")
  			{
  				break;
  			}
  			if(pd=="DIST")
  			{
  				cin>>u>>v;
  				cout<<dis[u]+dis[v]-2*dis[lca(u,v)]<<endl;
  			}
  			if(pd=="KTH")
  			{
  				cin>>u>>v>>k;
  				cout<<query_fa(u,v,k)<<endl;
  			}
  		}
  	}
  	return 0;
  }
  

luogu P3216 [HNOI2011]数学作业

luogu P2233 [HNOI2002] 公交车路线

luogu P4159 [SCOI2009] 迷路

• 令 \(f_{i,j}\) 表示第 \(i\) 时刻走到 \(j\) 的不同路径数量。状态转移方程为 \(f_{i,j}=\sum\limits_{(k,j) \in E}^{}[i-dis_{k,j} \ge 0] \times f_{i-dis_{k,j},k}\) ；特别地，规定 \(f_{0,1}=1\) 。

luogu P2151 [SDOI2009] HH去散步

luogu P3193 [HNOI2008]GT考试