首页 > 代码库 > 【uoj261】 天天爱跑步

【uoj261】 天天爱跑步

2024-08-26 12:44:00   222人阅读

http://uoj.ac/problem/261 (题目链接)

题意

　　给出一棵树，给出一些起点和终点，没走一条路径耗费时间1，每个节点上有一个权值w，问有多少条路径经过这个节点时所用的时间恰好是w。

Solution

　　转自：http://blog.csdn.net/haarmony/article/details/53259338

　　约定第${i}$个人起终点的${lca(s[i],t[i])}$为${lca[i]}$，点${i}$深度为${deep[i]}$

  • 考虑可能对点${u}$有贡献的第${i}$个跑步者，${lca[i]}$肯定在${u}$或者${u}$上方，否则不经过${u}$点，即${lca[i]==u || lca[i]∉subtree[u]}$
  • 基于此前提，只有两种情况（有重合部分）：${s[i]∈subtree[u]}$，${t[i]∈subtree[u]}$ 
    分类讨论能被${u}$看见的点${v}$的情况 
    　　1.${v}$为${i}$人起点${s[i]}$：${deep[s[i]]-w[u]==dep[u]}$ 
    　　2.${v}$为${i}$人终点${t[i]}$：${deep[s[i]]+deep[t[i]]-2*deep[lca[i]]-(deep[t[i]]-deep[u])==w[u]}$，即${deep[s[i]]-2*deep[lca[i]]==w[u]-deep[u]}$

　　我们发现如果做个变换，即${deep[u]+w[u]==deep[s[i]]}$

　　与${w[u]-deep[u]==deep[s[i]]-2*deep[lca[i]]}$的话，式子右边是不变的，那是不是可以开一个${cnt}$数组来统计一下子树中等于右式的出发点和结束点的个数呢？

    • 考虑使用${cnt[2][600600]}$存储起点/终点的${deep[s[i]]}$/${deep[s[i]]-2*deep[lca[i]]}$等于${j}$的点的数量，保存在数组${cnt[0 or 1][j]}$中，那么当dfs中当前点到${u}$的时候，${ans[u]}$就可以从cnt数组中得到，特殊情况是：${u}$为第${i}$人的lca时可能导致${s[i]}$与${t[i]}$各对${ans[u]}$贡献一次，所以式子如下
    • ${ans[u]=cnt[0][dep[u]+w[u]]+cnt[0][w[u]-dep[u]]-重复部分}$。两下标为上面两个等式的左式，需要注意的是${dep[s[i]]-2*dep[lca[i]]}$有可能是负数，下标可以统一+300000处理成正数（否则挂成50分）。其中重复部分可以在消除lca标记的时候判掉。
    • 维护cnt数组的方式容易想到就是在${s[i],t[i],lca[i]}$上打标记，若当前点为${s[i]}$就计入${cnt[0][dep[s[i]]]}$，${t[i]}$同理，${lca[i]}$就把两个标记再退出去
    • 然而如果对于每颗子树建立一个cnt，再把cnt合并的话，复杂度是n^2的。于是发现搜到以v为根的子树时后，对v贡献的只有两个下标，那么在搜索点v前，传两个参数a,b记录一下原来的cnt两个值，dfs(v,a,b)时${ans[v]-=a+b}$即可

细节

　　细节很多，想清楚再写。

代码

// uoj261#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#define inf 2147483640#define LL long long#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int T=300000,maxn=300010;struct edge {int to,next;}e[maxn<<1],g[maxn],ct[maxn];int cnt[2][10000010],h[maxn],hh[maxn],head[maxn];int deep[maxn],fa[maxn][30],bin[30],Lca[maxn];int n,m,c1,c2,c3,ans[maxn],cs[maxn],w[maxn],s[maxn],t[maxn];void linke(int u,int v) {	e[++c1].to=v;e[c1].next=head[u];head[u]=c1;	e[++c1].to=u;e[c1].next=head[v];head[v]=c1;}void linkg(int u,int v) {g[++c2].to=v;g[c2].next=h[u];h[u]=c2;}void linkt(int u,int v) {ct[++c3].to=v;ct[c3].next=hh[u];hh[u]=c3;}void dfs(int x) {	for (int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];	for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa[x][0]) {			fa[e[i].to][0]=x;			deep[e[i].to]=deep[x]+1;			dfs(e[i].to);		}}int lca(int x,int y) {	if (deep[x]<deep[y]) swap(x,y);	int t=deep[x]-deep[y];	for (int i=0;bin[i]<=t;i++) if (bin[i]&t) x=fa[x][i];	for (int i=20;i>=0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];	return x==y ? x : fa[x][0];}void dfs(int x,int ta,int tb) {	for (int j,i=head[x];i;i=e[i].next) if (e[i].to!=fa[x][0]) {			j=e[i].to;			dfs(j,cnt[0][w[j]+deep[j]+T],cnt[1][w[j]-deep[j]+T]);		}	cnt[0][deep[x]+T]+=cs[x];	for (int j,i=hh[x];i;i=ct[i].next) {		j=ct[i].to;		cnt[1][deep[s[j]]-deep[Lca[j]]*2+T]++;	}	ans[x]+=cnt[0][w[x]+deep[x]+T]+cnt[1][w[x]-deep[x]+T]-ta-tb;	for (int j,i=h[x];i;i=g[i].next) {		j=g[i].to;		if (w[x]+deep[x]==deep[s[j]]) ans[x]--;		cnt[0][deep[s[j]]+T]--;cnt[1][deep[s[i]]-2*deep[x]+T]--;	}}int main() {	bin[0]=1;for (int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;	scanf("%d%d",&n,&m);	for (int u,v,i=1;i<n;i++) {		scanf("%d%d",&u,&v);		linke(u,v);	}	dfs(1);	for (int i=1;i<=n;i++) scanf("%d",&w[i]);	for (int i=1;i<=m;i++) {		scanf("%d%d",&s[i],&t[i]);		Lca[i]=lca(s[i],t[i]);cs[s[i]]++;		linkg(Lca[i],i);		linkt(t[i],i);	}	dfs(1,0,0);	for (int i=1;i<=n;i++) printf("%d ",ans[i]);	return 0;}

　　

【uoj261】 天天爱跑步


联系
我们