題目描述

有一顆 \(n\) 個節點的樹，樹上的每一個點有一個爆炸半徑 \(r_i\)，每條邊 \((a_i,b_i)\) 有一個長度 \(c_i\)，一個炸彈 \(i\) 能引爆另一個炸彈 \(j\) 當且僅當 \(dis(i,j)\le r_i\)。

問題分析

我們可以建一個有向圖 \(G\)，對于 \(\forall i,j\ dis(i,j)\le r_i\) 建一條有向邊 \(i\to j\)，但顯然我們不可能接受這種數量級達到 \(n^2\) 的建邊方法，我們不妨進行點分治優化建圖，對于每次子樹的重心 \(i\) ,求子樹中每個點 \(j\) 到 \(i\) 的距離 \(dis_j\)，并按 \(dis_j\) 從小到大排序 \(j\) 得到序列 \(a\)，那么 \(dis(i,j)\le r_i\) 改寫成 \(dis_i+dis_j\le r_i\)，即 \(dis_j\le r_u-dis_i\)，我們不難發現點 \(i\) 可以連的點 \(j\) 是序列 \(a\) 的前綴。所以我們又可以前綴優化建圖，二分找到前綴的結束位置 \(k\)，將 \(i\) 連接到對應區間 \(a_1\) 到 \(a_k\) 的虛點上，然后將所有建出來的虛點相鄰連接，并且將相鄰虛點 \(i\) 與 \(j\) 之間的實點部分與 \(j\) 相連。具體化地可以見下圖：

（這張圖代表的是實點 \(1\) 到 \(3\) 的前綴區間為 \([1,1]\)，實點 \(4\) 到 \(5\) 的前綴區間為 \([1,3]\) 時的連邊情況，其中虛點 \(1\) 代表實點區間 \([1,1]\)，虛點 \(2\) 代表實點區間 \([1,3]\)）

通過前綴和與點分治優化建圖我們可以將 \(n^2\) 條邊優化到 \(n\log n\) 條邊。
接下來我們便可以對有向圖 \(G\) 進行縮點，對于每個 SCC 內的點，他們之間是可以互相引爆的，于是我們只需判斷 SCC 之間的可達性便可以了，顯然我們使用 bitset，但如果對于每個 SCC 開一個 bitset，那么空間上必然不優，將達到 \(O(\frac{n^2\log n}{w})\)，所以我們對 SCC 進行分塊，每次僅處理 \(bl\) 個 SCC 之間的可達性，空間復雜度降至 \(O(\frac{n\cdot bl\log n}{w})\)，時間復雜度依然為 \(O(n\log^2n+\frac{n^2\log n}{\omega})\)，經實測檢驗當 \(bl=2000\) 很優。

CODE

#include<bits/stdc++.h>
using namespace std;
namespace fastio{
	#define il inline
	const int isz=1<<25;
	char iin[isz],*is=iin+isz,*it=iin+isz;
	#define gc() (is==it)?(it=(is=iin)+fread(iin,1,isz,stdin),(is==it)?EOF:*is++):*is++
	template<typename T> il void rd(T &x){
		x=0;
		char c=gc();
		bool fla=false;
		while(!isdigit(c)) fla|=(c=='-'),c=gc();
		while(isdigit(c)) x=(x<<1)+(x<<3)+(c&15),c=gc();
		x=(fla)?-x:x;
	}
	template<typename T1,typename...T2> il void rd(T1 &x,T2&...y){rd(x);rd(y...);}
	template<typename T> il void rd(T a[],T s,T t){for(T i=s;i<=t;i++) rd(a[i]);}
	char iout[isz],*ita=iout;
	#define Flush() fwrite(iout,1,ita-iout,stdout);ita=iout
	template<typename T> il void wr(T x,char la='\n'){
		char c[35];
		int len=0;
		if(x<0) *ita++='-',x=-x;
		do{c[++len]=(x%10+'0');x/=10;}while(x);
		while(len)*ita++=c[len--];
		*ita++=la;
	} 
	il void en(char x){*ita++=x;}
}
using namespace fastio;
const int N=1e5+5,bl=2000;
#define int long long
int n,r[N],sz[N],del[N],dis[N],vir[N],tot,dfn[20*N],low[20*N],in[20*N],idx,id[20*N],scc,num,ans[N];
vector<int> e[N],w[N],g[20*N];
vector<pair<int,int> > line;
stack<int> q;
pair<int,int> s[400*N];
bitset<bl+10> f[20*N];
int rt_check(int x,int fa,int y,int &rt){
    sz[x]=1;
    int maxx=0;
    for(auto i:e[x])if(i!=fa&&!del[i]){rt_check(i,x,y,rt);sz[x]+=sz[i];maxx=max(maxx,sz[i]);}
    maxx=max(maxx,y-sz[x]);
    if((maxx<<1)<=y) rt=x;
    return sz[x];
}
void cal(int x,int fa){
    sz[x]=1;
    line.push_back({dis[x],x});
    for(int i=0;i<e[x].size();i++) if(e[x][i]!=fa&&!del[e[x][i]]){dis[e[x][i]]=dis[x]+w[x][i];cal(e[x][i],x);sz[x]+=sz[e[x][i]];}
}
void dfs(int x,int sz){
    if(sz==1) return;
    int rt;
    rt_check(x,x,sz,rt);
    del[rt]=1;
    dis[rt]=0;
    line.clear();
    cal(rt,rt);
    sort(line.begin(),line.end());
    memset(vir,0,sizeof vir);
    for(auto i:line){
        int ttt=upper_bound(line.begin(),line.end(),make_pair(r[i.second]-dis[i.second],n+1))-line.begin();
        ttt--;
        if(ttt>=0){if(!vir[ttt]){vir[ttt]=++tot;g[tot].push_back(line[ttt].second);}g[i.second].push_back(vir[ttt]);}
    }
    int la=-1;
    for(int i=line.size()-1;i>=0;i--) 
        if(vir[i]){
            if(la!=-1){
                g[vir[la]].push_back(vir[i]);
                for(int j=i+1;j<la;j++) g[vir[la]].push_back(line[j].second);
            }
            la=i;
        }
    if(la!=-1)for(int j=0;j<la;j++)g[vir[la]].push_back(line[j].second);
    for(auto i:e[rt]) if(!del[i]) dfs(i,::sz[i]);
}
void tarjan(int x){
    dfn[x]=low[x]=++idx;
    in[x]=1;
    q.push(x);
    for(auto i:g[x]){if(!dfn[i]){tarjan(i);low[x]=min(low[x],low[i]);}else if(in[i])low[x]=min(low[x],dfn[i]);}
    if(low[x]==dfn[x]){++scc;int ttt;do{ttt=q.top();q.pop();in[ttt]=0;id[ttt]=scc;}while(ttt!=x);}
}
signed main(){
    rd(n);
    rd(r,1ll*1,n);
    for(int i=1;i<n;i++){int x,y,z;rd(x,y,z);e[x].push_back(y);e[y].push_back(x);w[x].push_back(z);w[y].push_back(z);}
    tot=n;
    dfs(1,n);
    for(int i=1;i<=tot;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=tot;i++) for(auto j:g[i]) if(id[i]!=id[j]) s[num++]={id[j],id[i]};
    int maxn=0;
    for(int i=1;i<=n;i++) maxn=max(maxn,id[i]);
    sort(s,s+num);
    num=unique(s,s+num)-s;
    auto solve=[maxn](int l,int r){
        for(int i=1;i<=maxn;i++) f[i].reset();
        for(int i=l;i<=r;i++) f[id[i]].set(i-l);
        for(int i=0;i<num;i++) f[s[i].second]|=f[s[i].first];
        for(int i=1;i<=n;i++) ans[i]+=f[id[i]].count();
    };
    for(int i=1;i<=n;i+=bl) solve(i,min(i+bl-1,n));
    for(int i=1;i<=n;i++) wr(ans[i],' ');
    Flush();
    return 0;
}