【CF791D】tree 檸檬樹

【題目描述】

Herobrine能掌控所有，除了他内心的那棵檸檬樹。

他每看到一件讓自己心生羨慕的事，他内心的檸檬樹上就會多長出一隻多汁美味的檸檬。

現在，Herobrine有一棵含有n隻檸檬的檸檬樹，編号從1到n。這n隻檸檬由n-1條樹枝相連。 檸檬之間很喜歡用脫落酸進行交流。脫落酸隻能通過樹枝傳遞。檸檬們為了盡量頻繁的進行交流，就團結一心，調整了樹枝的形态，使得任意兩隻不同的檸檬之間都有且僅有一條傳遞脫落酸的通路。

我們知道檸檬樹上的檸檬和Herobrine有着深仇大恨。這也就是為什麼檸檬樹上的檸檬要盡可能地進行交流——交流時，脫落酸的傳輸會消去Herobrine的頭發，使得他看起來很難看。檸檬們很喜歡這樣。但是存在一個特例。Herobrine告訴你，若有兩隻檸檬的編号為a和b，且a＜b，那麼a将脫落酸傳輸給b時，Herobrine的頭發會消去，但當b将脫落酸傳輸給a時，Herobrine的頭發不會消去。

Herobrine想知道一下檸檬樹對他頭發的威力。Herobrine又告訴你，不僅任意兩隻檸檬都能進行交流，而且兩隻檸檬在交流的過程中，脫落酸每傳播一段路程，就會使Herobrine掉一根頭發。Herobrine告訴你一個常數，叫卡常數k。這意味着，每當脫落酸傳播k根樹枝時，Herobrine的頭發就會掉一根。

你是個好問的孩子。你會問，如果脫落酸傳播了k-1根樹枝，頭發會掉嗎？

“廢話！你看看我的頭頂！當然了！”

Herobrine告訴你一個簡潔的方法，用來判斷一次交流會掉幾根頭發。如果脫落酸傳播了m根樹枝，Herobrine就會掉 ⌈ m k ⌉ \left \lceil \frac{m}{k} \right \rceil ⌈km​⌉根頭發。

“看！檸檬們都開始交流了！”Herobrine痛苦地捂住他那像做過817次化療後的頭頂。現在，**每隻檸檬都會和其它所有的檸檬通過樹枝用脫落酸進行交流。**那麼，有多少次交流會使得Herobrine掉發呢？

【輸入格式】

輸入第一行包括三個用空格隔開的整數case,n,k。case代表測試資料編号。n,k的含義見題目描述。

輸入第二行至第n行，每行包括兩個用空格分開的整數a，b，表示檸檬a與檸檬b之間有樹枝相連。

【輸出格式】

輸出一行一個整數，表示會使得Herobrine掉發的交流的次數。

【樣例輸入1】

1 6 2

1 2

1 3

2 4

2 5

4 6

【樣例輸出1】

20

【Hint】

n<=2e5,k<=5

—【感謝excitedfrog友情編題】

【分析】

接近于求樹上路徑和，但對路徑和進行了一些奇怪的處理，但是依然可以用點分治解決。這裡由于k非常小，是以點分治的合并操作時可以通過枚舉餘數來進行高效的合并。（憑着殘缺的記憶，我竟然首次把點分治打對了，雖然合并時出了鍋，跑）

【code】

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int casex,n,k;
ll ans;
int num,hed[150010],nex[300010],vt[300010];
int vi[150010],sum[150010],mx[150010],sumx,root;
ll dep[150010],nn[10],le[10],ccc;

int read(){
	int u=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') u=(u<<1)+(u<<3)+c-'0',c=getchar();
	return u;
}

void add(int x,int y){
	vt[++num]=y,nex[num]=hed[x],hed[x]=num;
	vt[++num]=x,nex[num]=hed[y],hed[y]=num;
}

void get_root(int u,int fa){
	sum[u]=0,mx[u]=0;
	for(int i=hed[u];i;i=nex[i]){
		if(vt[i]==fa||vi[vt[i]]) continue;
		get_root(vt[i],u);
		sum[u]+=sum[vt[i]],mx[u]=max(mx[u],sum[vt[i]]);
	}
	sum[u]++,mx[u]=max(mx[u],sumx-sum[u]);
	if(mx[u]<mx[root]) root=u;
}

void get_dep(int u,int fa,int l){
	dep[++ccc]=l;
	for(int i=hed[u];i;i=nex[i]){
		if(vi[vt[i]]||vt[i]==fa) continue;
		get_dep(vt[i],u,l+1);
	}
}

ll get_ans(int u,int l){
	ll res=0;
	ccc=0;
	get_dep(u,0,l);
	memset(nn,0,sizeof(nn)),memset(le,0,sizeof(le));
	for(int i=1;i<=ccc;i++) le[dep[i]%k]+=dep[i]/k,nn[dep[i]%k]++;
	for(int i=0;i<=k;i++){
		if(i!=0) res+=(i*2>k?nn[i]*(nn[i]-1):nn[i]*(nn[i]-1)/2);
		res+=le[i]*(nn[i]-1);
		for(int j=i+1;j<=k;j++) res+=(i+j>k?nn[i]*nn[j]*2:nn[i]*nn[j])+le[i]*nn[j]+le[j]*nn[i];
	}
	return res;
}

void dfs(int u){
	vi[u]=1,ans+=get_ans(u,0);
	for(int i=hed[u];i;i=nex[i]){
		if(vi[vt[i]]) continue;
		ans-=get_ans(vt[i],1);
		sumx=sum[vt[i]],root=0,get_root(vt[i],u),dfs(root);
	}
}

int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	casex=read(),n=read(),k=read();mx[0]=n;
	for(int i=1;i<=n-1;i++){
		int x=read(),y=read();
		add(x,y);
	}
	sumx=n;
	get_root(1,0);
	dfs(root);
	printf("%lld",ans);
}
           

【另一個解法】樹形dp一維記節點，二維記餘數，容斥一下，複雜度nk。