【TIOJ 1775】失誤分支的結局

原題連結：https://tioj.ck.tp.edu.tw/problems/1775

久違的文章(?
被某人丟了這題，發現原本這題只有一個人過
本來以為不太可做，結果想了一下發現似乎有那麼一點希望(?)，就花了一段時間刻出來了ww

首先從水母圖的角度切入，很顯然的這是把很多棵樹的根節點連成一個環所形成的圖
接下來就能發現，只要將環上每個點的子樹的所有距離(包含自己)，分別記錄起來排序
且如果環的大小是$\color{white}{\space L\space}$，則對於每個點，得到「點到環的距離」後就可以枚舉環上的每個點二分搜得到除了自己這棵樹以外符合題目條件的個數了。
這裡只花了$\color{white}{\space O(NLlgN)\space}$

所以接下來我們就能把題目縮減成在樹上的子問題，只要把環切開來一個一個做就好了。
這樣的話我們先來考慮一個類似的小問題：

「給定長度為$\color{white}{\space N\space}$的兩個序列$\color{white}{\space d_i\space}$和$\color{white}{\space k_i\space}$，如果我把序列切成$\color{white}{\space M\space}$塊，試問對於每個$\color{white}{\space i\space}$，滿足$\color{white}{\space d_i+d_j<=k_i\space}$的整數$\color{white}{\space j\space}$，且$\color{white}{\space i,j\space}$不在同一塊的個數有多少個？」

總之會有$\color{white}{\space O(NlgN)\space}$的作法

同樣的問題要如何對應到樹上面呢？

－－沒錯，就是樹分治！
對於每一棵需要求該問題的樹，我們把這棵樹的重心拆掉之後遞迴下去
在合併一堆小樹時，從重心$\color{white}{\space dfs\space}$出去記錄其他點到自己的距離$\color{white}{\space d_i\space}$，這樣若有$\color{white}{\space M\space}$棵小樹，就對應到上面那個問題了！(不過要記得算上重心本身～)

由於拔掉重心後可以保證任一棵小樹的大小不超過$\color{white}{\space \dfrac{N}{2} \space}$
所以最慘的分治情況就會出現在完美二元樹上，會得到類似三維偏序問題的複雜度$\color{white}{\space O(Nlg^2N)\space}$。

總複雜度$\color{white}{\space O(Nlg^2N+NLlgN)\space}$！

附上code，還蠻可怕的，如果有看不下去的請指教(?)：

	#pragma GCC optimize("Ofast")
	#include <bits/stdc++.h>
	#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	#define pb push_back
	#define F first
	#define S second
	#define MEM(i,j) memset(i,j,sizeof i)
	#define MP make_pair
	#define ET cout << "\n"
	#define DB(a,s,e) {for(int i=s;i<e;i++) cout << a[i] << " ";ET;}
	using namespace std;
	typedef long long ll;
	typedef pair<int,int> pii;
	bitset<100001> vis,roll,no;
	bitset<20> has;
	vector<int> child[100001],v[100001];
	int e,w[100001],h[100001],d[100001],ans[100001],k[100001],bit[100001],n,be[100001],fun[100001],td[100001];
	bool dfs(int x,int f)
	{
	vis[x]=1;
	for(int i:child[x])
	if(!vis[i])
	roll[x]=dfs(i,x)|roll[x];
	else if(i!=f & !roll[i]) roll[x]=1,e=i;
	return x!=e && roll[x];
	}
	void dfs2(int x,int u,int f)
	{
	vis[x]=1,h[x]=f,d[x]=u,v[f].pb(u);
	for(int i:child[x])
	if(!vis[i] && !roll[i])
	dfs2(i,u+1,f);
	}
	int lowbit(int x)
	{
	return x&-x;
	}
	void modify(int x,int v)
	{
	for(++x;x<=n;x+=lowbit(x)) bit[x]+=v;
	}
	int query(int x)
	{
	int re=0;
	for(++x;x;x-=lowbit(x)) re+=bit[x];
	return re;
	}
	void dfs3(int x,int t,vector<int> &c)
	{
	fun[x]=t,c.pb(x),w[x]=1;
	for(int i:child[x])
	if(!roll[i] && !no[i] && fun[i]!=t)
	dfs3(i,t,c),w[x]+=w[i];
	}
	void dfs4(int x,int u,int t,int hv)
	{
	fun[x]=t,td[x]=u;
	if(td[x]<=k[hv]) ++ans[hv];
	for(int i:child[x])
	if(!roll[i] && !no[i] && fun[i]!=t)
	dfs4(i,u+1,t,hv);
	}
	vector<int> solve(int x)
	{
	vector<int> c;
	vector<vector<int>> jiz;
	int wei=n,hv,tmp;
	dfs3(x,fun[x]+1,c);
	for(int i:c)
	{
	tmp=0;
	for(int j:child[i])
	if(w[j]<w[i]) tmp=max(w[j],tmp);
	else tmp=max(tmp,w[x]-w[i]);
	if(tmp<wei) wei=tmp,hv=i;
	}
	no[hv]=1;
	for(int i:child[hv])
	if(!roll[i] && !no[i])
	jiz.pb(solve(i));
	dfs4(hv,0,fun[hv],hv);
	for(auto i:jiz)
	for(int j:i)
	modify(td[j],1);
	for(auto i:jiz)
	{
	for(int j:i)
	modify(td[j],-1);
	for(int j:i)
	if(k[j]>=td[j])
	ans[j]+=query(min(n-1,k[j]-td[j]))+1;
	for(int j:i)
	modify(td[j],1);
	}
	for(auto i:jiz)
	for(int j:i)
	modify(td[j],-1);
	no[hv]=0;
	return c;
	}
	void bfs(int x,int f,int d)
	{
	queue<pii> q;
	q.push(MP(x,d)),has[be[x]]=1;
	while(!q.empty())
	{
	auto p=q.front();
	q.pop();
	if(p.F!=h[f])
	ans[f]+=upper_bound(v[p.F].begin(),v[p.F].end(),p.S)-v[p.F].begin();
	if(p.S)
	for(int i:child[p.F])
	if(roll[i] && !has[be[i]])
	q.push(MP(i,p.S-1)),has[be[i]]=1;
	}
	}
	int main()
	{jizz
	int a,b,t=0;
	cin >> n;
	for(int i=0;i<n;++i)
	cin >> a >> b,child[a].pb(b),child[b].pb(a);
	for(int i=1;i<=n;++i)
	cin >> k[i];
	dfs(1,0),vis.reset();
	for(int i=1;i<=n;++i)
	if(roll[i])
	dfs2(i,0,i),sort(v[i].begin(),v[i].end()),roll[i]=0,solve(i),roll[i]=1,be[i]=t++;
	for(int i=1;i<=n;++i)
	if(k[i]>=d[i]) has.reset(),bfs(h[i],i,k[i]-d[i]);
	for(int i=1;i<=n;++i)
	cout << ans[i] << "\n";
	}

view raw gistfile1.txt hosted with ❤ by GitHub