Description
http://www.lydsy.com/JudgeOnline/upload/201712/prob12.pdf
Input
Output
暑假集训的时候点分树做的比较少，所以做这道题比较吃力，然而现在看这道题就比较简单了.
考虑直接建立点分树，每一个节点只需维护点分子树中 $BFS$ 序.
这样的好处是子树中点的深度是连续的，所以每次能到达的点肯定是连续的区间.
那么，只需按照 $Dijkstra$ 的运行过程，将点加入到优先队列中，并扩展队首.
每次扩展只需边删掉 $BFS$ 序中可以到达的点并加入到堆中，然后一边跳点分树中父亲即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=300005;
namespace IO {
void setIO(string s) {
string in=s+".in";
string out=s+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {
int x=0;
char c=nc();
while(c<48) c=nc();
while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc();
return x;
}
};
namespace tree{
int edges;
int hd[maxn],to[maxn<<1],nex[maxn<<1];
int fa[maxn],top[maxn],siz[maxn],son[maxn],dep[maxn];
void addedge(int u,int v) {
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
void dfs1(int u,int ff) {
dep[u]=dep[ff]+1,fa[u]=ff,siz[u]=1;
for(int i=hd[u];i;i=nex[i]) {
int v=to[i];
if(v==ff) continue;
dfs1(v,u), siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int tp) {
top[u]=tp;
if(son[u]) dfs2(son[u],tp);
for(int i=hd[u];i;i=nex[i]) {
int v=to[i];
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
int LCA(int x,int y) {
while(top[x]^top[y]) {
dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
}
return dep[x]<dep[y]?x:y;
}
int Dis(int x,int y) {
return dep[x]+dep[y]-(dep[LCA(x,y)]*2);
}
};
namespace Divide {
struct Node {
int dis,u;
Node(int dis=0,int u=0):dis(dis),u(u){}
}st[maxn],val[maxn*30];
queue<Node>q;
int mn,root,tp,edges;
int siz[maxn],mx[maxn],mark[maxn],Fa[maxn],in[maxn],hd[maxn],to[maxn*30],nex[maxn*30];
void Add(int u,Node e) {
nex[++edges]=hd[u],hd[u]=edges,val[edges]=e;
}
void getroot(int u,int ff) {
mx[u]=0, siz[u]=1;
for(int i=tree::hd[u];i;i=tree::nex[i]) {
int v=tree::to[i];
if(v==ff||mark[v]) continue;
getroot(v,u), siz[u]+=siz[v];
mx[u]=max(mx[u],siz[v]);
}
mx[u]=max(mx[u], mn-siz[u]);
if(mx[u] < mx[root]) root=u;
}
void bfs(int u) {
tp=0;
q.push(Node(0,u));
in[u]=u;
while(!q.empty()) {
Node e=q.front(); q.pop();
st[++tp]=e;
int x=e.u;
for(int i=tree::hd[x];i;i=tree::nex[i]) {
int v=tree::to[i];
if(mark[v]||in[v]==u) continue;
in[v]=u;
q.push(Node(e.dis+1,v));
}
}
for(int i=tp;i>=1;--i) Add(u, st[i]);
}
void divide(int u) {
mark[u]=1;
bfs(u);
for(int i=tree::hd[u];i;i=tree::nex[i]) {
int v=tree::to[i];
if(mark[v]) continue;
root=0,mn=siz[v],getroot(v,u);
Fa[root]=u;
divide(root);
}
}
void pre(int n) {
mx[0]=1000000000,mn=n,root=0,getroot(1,0);
divide(root);
}
};
int n,S;
int L[maxn];
ll C[maxn];
namespace Dijkstra {
ll d[maxn];
int flag[maxn];
struct Node {
ll dis;
int u;
Node(ll dis=0,int u=0):dis(dis),u(u){}
bool operator<(Node b) const {
return dis>b.dis;
}
};
priority_queue<Node>q;
void del(int x,int limit,ll ge,int u) {
if(limit<0) return;
while(Divide::hd[x] && Divide::val[Divide::hd[x]].dis<=limit) {
int v=Divide::val[Divide::hd[x]].u;
Divide::hd[x]=Divide::nex[Divide::hd[x]];
if(flag[v]) continue;
d[v]=ge, flag[v]=1, q.push(Node(d[v] + C[v], v));
}
if(Divide::Fa[x]) del(Divide::Fa[x],L[u]-tree::Dis(u,Divide::Fa[x]),ge,u);
}
void solve() {
d[S]=0,flag[S]=1;
q.push(Node(C[S],S));
while(!q.empty()) {
Node e=q.top(); q.pop();
del(e.u, L[e.u], e.dis, e.u);
}
}
};
int main() {
using namespace IO;
// setIO("input");
n=rd(),S=rd();
for(int i=1;i<n;++i) {
int u=rd(),v=rd();
tree::addedge(u,v);
tree::addedge(v,u);
}
tree::dfs1(1,0);
tree::dfs2(1,1);
for(int i=1;i<=n;++i) L[i]=rd(), C[i]=(ll)rd();
Divide::pre(n);
Dijkstra::solve();
for(int i=1;i<=n;++i) printf("%lld
",Dijkstra::d[i]);
return 0;
}