正题
题目链接:https://www.luogu.org/problemnew/show/P1600
题目大意
一棵
n
n
n个点的树，通过每条边需要时间为1。有
m
m
m个玩家从
S
i
S_i
Si跑到
T
i
T_i
Ti（不停留，跑完之后马上消失）。然后对于第
i
i
i个点求第
w
i
w_i
wi刻停留在改点的玩家数量。
解题思路
对于每条路径我们拆分成两段，算是树上差分的一个变形
自
S
−
>
l
c
a
S->lca
S−>lca，然后当该路径上一个点满足
d
e
p
i
+
w
i
=
d
e
p
S
dep_i+w_i=dep_S
depi+wi=depS则经过改点。 对于这种情况，我们用
c
n
t
i
cnt_i
cnti表示起点为
i
i
i的人个数，
V
s
i
Vs_i
Vsi表示
l
c
a
lca
lca在
i
i
i点的路径的起点深度集合。然后用
v
u
p
i
vup_i
vupi表示目前
d
e
p
S
=
i
dep_S=i
depS=i的路径个数自
l
c
a
−
>
E
lca->E
lca−>E，然后当改点上一个点满足
d
e
p
i
−
w
i
=
2
∗
d
e
p
l
c
a
−
d
e
p
s
dep_i-w_i=2*dep_{lca}-dep_s
depi−wi=2∗deplca−deps则经过改点。 为了方便陈述，我们定义
n
u
m
=
2
∗
d
e
p
l
c
a
−
d
e
p
s
num=2*dep_{lca}-dep_s
num=2∗deplca−deps 对于这种情况，我们用
c
n
t
2
i
cnt2_i
cnt2i表示终点为
i
i
i的路径
n
u
m
num
num集合，
V
t
i
Vt_i
Vti表示
l
c
a
lca
lca在
i
i
i点的路径的
n
u
m
num
num集合。然后用
v
d
o
w
n
i
vdown_i
vdowni表示目前
n
u
m
=
i
num=i
num=i的路径个数
然后就完成了，不过要注意
d
e
p
i
−
w
i
dep_i-w_i
depi−wi可能为负数所以我们需要加上一个大整数
N
N
N。(
P
a
s
c
a
l
Pascal
Pascal就莫得问题了)
c
o
d
e
code
code
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>
using namespace std
;
const int N
=310000;
struct line
{
int to
,next
;
}a
[N
*5];
int tot
,n
,m
,ls
[N
],dep
[N
],f
[N
][30];
int vup
[4*N
],vdown
[4*N
],cnt
[N
],T
,ans
[N
],w
[N
];
vector
<int> Vs
[N
],Vt
[N
],cnt2
[N
];
queue
<int> q
;
inline int read()
{
int X
=0,w
=0; char c
=0;
while(c
<'0'||c
>'9') {w
|=c
=='-';c
=getchar();}
while(c
>='0'&&c
<='9') X
=(X
<<3)+(X
<<1)+(c
^48),c
=getchar();
return w
?-X
:X
;
}
inline void addl(int x
,int y
)
{
a
[++tot
].to
=y
;
a
[tot
].next
=ls
[x
];
ls
[x
]=tot
;
}
inline void bfs(int s
)
{
q
.push(s
);dep
[s
]=1;
while(!q
.empty())
{
int x
=q
.front();q
.pop();
for (int i
=ls
[x
];i
;i
=a
[i
].next
)
{
int y
=a
[i
].to
;
if (dep
[y
]) continue;
q
.push(y
);f
[y
][0]=x
;
dep
[y
]=dep
[x
]+1;
}
}
T
=(int)(log(n
)/log(2))+1;
for (int j
=1;j
<=T
;j
++)
for (int i
=1;i
<=n
;i
++)
f
[i
][j
]=f
[f
[i
][j
-1]][j
-1];
}
inline int LCA(int x
,int y
)
{
if (dep
[x
]>dep
[y
]) swap(x
,y
);
for (int i
=T
;i
>=0;i
--)
if (dep
[f
[y
][i
]]>=dep
[x
]) y
=f
[y
][i
];
if (x
==y
) return x
;
for (int i
=T
;i
>=0;i
--)
if (f
[y
][i
]!=f
[x
][i
])
{
x
=f
[x
][i
];
y
=f
[y
][i
];
}
return f
[x
][0];
}
void dfs(int x
,int fa
)
{
int nup
=dep
[x
]+w
[x
]+N
,ndown
=dep
[x
]-w
[x
]+N
;
int last
=vup
[nup
]+vdown
[ndown
];
vup
[dep
[x
]+N
]+=cnt
[x
];
for(int i
=0;i
<cnt2
[x
].size();i
++)
vdown
[cnt2
[x
][i
]+N
]++;
for(int i
=0;i
<Vs
[x
].size();i
++)
vup
[Vs
[x
][i
]+N
]--;
for(int i
=0;i
<Vt
[x
].size();i
++)
vdown
[Vt
[x
][i
]+N
]--;
for(int i
=ls
[x
];i
;i
=a
[i
].next
)
{
int y
=a
[i
].to
;
if(y
==fa
) continue;
dfs(y
,x
);
}
ans
[x
]+=vup
[dep
[x
]+w
[x
]+N
]+vdown
[dep
[x
]-w
[x
]+N
]-last
;
}
int main()
{
n
=read();m
=read();
for(int i
=1;i
<n
;i
++){
int x
,y
;
x
=read();y
=read();
addl(x
,y
);addl(y
,x
);
}
for(int i
=1;i
<=n
;i
++)
w
[i
]=read();
bfs(1);
for(int i
=1;i
<=m
;i
++){
int s
,t
;
s
=read();t
=read();
int lca
=LCA(s
,t
);
cnt
[s
]++;Vs
[f
[lca
][0]].push_back(dep
[s
]);
cnt2
[t
].push_back(2*dep
[lca
]-dep
[s
]);
Vt
[lca
].push_back(2*dep
[lca
]-dep
[s
]);
}
dfs(1,1);
for(int i
=1;i
<=n
;i
++)
printf("%d ",ans
[i
]);
}
