严肃话一个上午调这题，写完发现TLE，优化后还是TLE，然后发现要写FFT分治，写一半发现自己优化的sort写错地方成功浪费1h

注释是AI写的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=acos(-1);
// 复数结构体，用于FFT运算
struct N{
	double x,y; // x:实部 y:虚部
};
N operator*(N a,N b){
	return {a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}
N operator+(N a,N b){
	return {a.x+b.x,a.y+b.y};
}
N operator-(N a,N b){
	return {a.x-b.x,a.y-b.y};
}
int r[800010]; // 位逆序置换数组
int n; // 节点总数
vector<int> e[200010]; // 邻接表
int sum,sz[200010],del[200010],rt,mn;
// sum:当前分治连通块大小
// sz[x]:x的子树大小
// del[x]:x是否已被作为重心删除
// rt:当前重心
// mn:找重心时记录的最小"最大子树"
bool cmp(int a,int b){
	return sz[a]<sz[b];
}
// 在包含x的连通块中找重心
void getrt(int x,int xfa){
	sz[x]=1;
	int mx=0;
	for(int y:e[x])if(y!=xfa&&!del[y]){
		getrt(y,x);
		mx=max(mx,sz[y]);
		sz[x]+=sz[y];
	}
	mx=max(mx,sum-sz[x]); // x"上方"部分的大小
	if(mx<mn){
		mn=mx;
		rt=x;
	}
}
// FFT，op=1正变换，op=-1逆变换
void FFT(N a[],int n,int op){
	for(int i=0;i<n;i++)if(i<r[i])swap(a[i],a[r[i]]);
	for(int m=2;m<=n;m<<=1){
		N w1={cos(2*pi/m),sin(2*pi/m)*op};
		for(int i=0;i<n;i+=m){
			N wk={1,0};
			for(int j=0;j<m/2;j++){
				N x=a[i+j],y=a[i+j+m/2]*wk;
				a[i+j]=x+y;a[i+j+m/2]=x-y;
				wk=wk*w1;
			}
		}
	}
}
// 多项式卷积：a[0..al-1] * b[0..bl-1]，结果存回a，al更新为结果长度
void solve(N a[],int &al,N b[],int bl){
	int pal=al; // 保存a原来的有效长度
	al=al+bl-1; // 卷积结果长度
	int n=1;
	while(n<al)n<<=1; // FFT需要的2的幂长度
	for(int i=0;i<n;i++)r[i]=r[i/2]/2+(i&1)*(n/2); // 位逆序
	for(int i=pal;i<n;i++)a[i]={0,0}; // 清零a中超出原有效范围的部分
	FFT(a,n,1);FFT(b,n,1); // 正变换
	for(int i=0;i<n;i++){
		a[i]=a[i]*b[i]; // 点值相乘
	}
	FFT(a,n,-1); // 逆变换
	for(int i=0;i<n;i++)b[i]={0,0}; // 清零b，防止残留影响下次
	for(int i=0;i<al;i++){
		a[i].x/=n;a[i].y=0; // 除以FFT长度，清除虚部浮点误差
	}
}
N now[800010],d[800010],h[800010];
// now:参与FFT卷积的距离分布（会被solve破坏，之后用h恢复）
// d:当前子树的距离分布，d[i].x=距重心为i的节点数
// h:累积的距离分布（重心+已处理的所有子树），不被solve破坏
ll ans[800010]; // ans[i]:距离为i的无序点对数
int mxdp,dis[800010],m;
// mxdp:当前子树中最大深度+1（即d数组的有效长度）
// dis[x]:x到当前重心的距离
// 收集子树中所有节点到重心的距离
void getdis(int x,int xfa){
	dis[x]=dis[xfa]+1;
	mxdp=max(mxdp,dis[x]+1); // 更新有效长度
	d[dis[x]].x+=1; // 该距离的节点数+1
	for(int y:e[x])if(y!=xfa&&!del[y])getdis(y,x);
}
// 处理重心x：统计所有经过x的路径
void calc(int x){
	del[x]=1; // 标记重心已删除
	int nl=1; // now的有效长度
	now[0]={1,0}; // 重心本身，距离0有1个点
	h[0]={1,0};   // h也包含重心
	sort(e[x].begin(),e[x].end(),cmp); // 按子树大小排序，小的先处理
	for(int y:e[x])if(!del[y]){
		mxdp=1; // d[0]不用（子树节点距重心至少为1），有效长度从1开始
		dis[x]=0;
		getdis(y,x); // 收集子树y的距离信息到d
		int nnl=max(nl,mxdp); // 合并后h的有效长度
		// 将当前子树d累加到h中
		for(int i=1;i<nnl;i++)h[i]=h[i]+d[i];
		// 卷积 now * d：统计"已有点集"与"当前子树"之间的配对
		solve(now,nl,d,mxdp);
		ll p2=1;
		while(p2<nl)p2<<=1;
		// 卷积结果累加到ans，然后用h恢复now
		for(int i=0;i<nl;i++){
			ans[i]=ans[i]+(ll)(now[i].x+0.5); // 四舍五入
			now[i]=h[i]; // 恢复now为累积分布h
		}
		nl=nnl; // 更新now的有效长度
	} 
	// 清零h，供下一层divide使用
	for(int i=0;i<nl;i++)h[i]={0,0};
}
// 点分治递归
void divide(int x){
	calc(x); // 处理当前重心
	for(int y:e[x])if(!del[y]){
		mn=sum=sz[y]; // 对子树y递归找重心
		getrt(y,x); 
		divide(rt);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;x++;y++; // 输入0-indexed，转为1-indexed
		e[x].push_back(y);
		e[y].push_back(x);
	}
	mn=sum=n;
	getrt(1,0);   // 找整棵树的重心
	getrt(rt,0);  // 再跑一次更新sz
	divide(rt);   // 开始点分治
	int p2=1;
	while(p2<n)p2<<=1;
	for(int i=1;i<n;i++)cout<<ans[i]<<" "; // 输出距离1~n-1的答案
	return 0;
}

本题思路 made by deepseek：

为了让你彻底理解“距离组合统计”和“去除同一子树贡献”的原理，我将从零推导点分治中统计路径的数学过程。

---

1. 点分治的统计目标

在点分治的当前重心 c 处，我们想要统计所有经过 c 的路径（即路径上的一个端点是 c 或者两个端点分属不同的子树）。
我们不会在当前层统计完全位于同一棵子树内部的路径，因为那些路径会在更小的子问题中处理。

---

2. 收集距离数据

我们以 c 为根，遍历整个连通块，记录每个节点到 c 的距离。

• 令 A 为所有节点到 c 的距离的多重集合（包含距离 0，即 c 本身）。
• 将 c 的每个邻居子树 T_i 的距离集合记为 S_i（这些距离均 ≥ 1）。

则有：

A = {0} ∪ S_1 ∪ S_2 ∪ ... ∪ S_k

---

3. 我们想要统计的路径

期望统计：所有满足 路径经过 c 的无序点对 (u, v)（u ≠ v）。

• 若 u = c，则 v 在某个子树中，路径经过 c，合法。
• 若 u 在 S_i，v 在 S_j（i ≠ j），则路径经过 c，合法。
• 若 u, v 在同一子树 S_i 内，则路径不经过 c，不应在当前层统计。

因此，当前层应统计的路径长度频次 = 所有来自不同子树的点对（包括 c 与各子树点）的路径长度之和。

---

4. 如何用集合的“全量减局部”实现

我们定义 F(X) 为集合 X 中所有无序点对的距离之和的频次（即对 X 中任意两个不同点，计算距离和，汇总频次）。
那么：

• F(A) 统计了 A 中所有不同点的点对，包括：

  1. c 与各子树点（跨子树，合法）
  2. 不同子树之间的点（跨子树，合法）
  3. 同一子树内部的点（不合法，应排除）

• 对于每个子树 S_i，F(S_i) 正好统计了该子树内部所有点对（不合法）。

因此，合法路径的频次 = F(A) - Σ F(S_i)。

因为 A 包含 {0} 和所有 S_i，而 S_i 内部点对在 F(A) 中被计入了一次，减去 F(S_i) 就恰好去掉它们。
而 c 与子树点的点对（0 与 S_i 中的点）只出现在 F(A) 中，不会被减去，所以被保留。

---

5. 距离组合统计的具体计算

现在问题转化为：给定一个距离多重集合 X，如何快速计算 F(X)？

5.1 频次数组

设 cnt[d] = 距离为 d 的元素个数（d ≥ 0）。

5.2 有序对与卷积

定义卷积 conv[s] = Σ_{d=0}^s cnt[d] * cnt[s-d]。

• conv[s] 表示所有有序对 (a, b) 的数量，其中 a 的距离为 d，b 的距离为 s-d，且 a 和 b 都是 X 中的元素（允许 a = b 同一个元素）。

5.3 自配对扣除

在 conv 中，自配对（即 a = b 同一个顶点）会被计入：对于每个距离为 d 的顶点，它在卷积中贡献了一个有序对 (v, v)，所以总自配对数量为 cnt[d]（每个顶点一个），这些出现在 conv[2d] 中（因为 d+d=2d）。
所以：

自配对贡献 self[2d] = cnt[d]

5.4 不同顶点的有序对数量

不同顶点的有序对（即 a ≠ b）的数量为：

ordered_diff[s] = conv[s] - self[s]

因为 conv[s] 包含了所有有序对（包括自配对），减去自配对即得到不同顶点的有序对。

5.5 无序对数量（我们需要的）

对于每个不同的无序点对 {u, v}（u ≠ v），它在 ordered_diff 中被计算了两次（(u,v) 和 (v,u)）。
因此：

F(X)[s] = ordered_diff[s] / 2 = (conv[s] - self[s]) / 2

5.6 注意

• s 的范围为 0 到 2*maxd，但我们只关心 1 ≤ s ≤ N-1，且距离为 0 的点对（即 u=v）我们不统计。
• 如果 (conv[s] - self[s]) 是奇数，可能是浮点误差，实际应为偶数，代码中做 if (val&1) val-- 处理。

---

6. 回到点分治

• 对 A 调用 F(A) 累加到答案（sign=+1）。
• 对每个 S_i 调用 F(S_i) 减去（sign=-1）。

最终答案 ans 就是所有路径距离的分布。

---

7. 为什么这样能保证不重不漏？

每个无序点对 (u, v) 在分治过程中，第一次被处理时，它们的路径所经过的最高重心（即在分治树中深度最小的重心）一定是路径上某个点。在该重心处，u 和 v 必然位于不同的子树（或其中一个就是重心），因此它们会被计入 F(A)，并且不会被任何 F(S_i) 减去（因为它们不在同一子树中）。之后递归到更小的子树时，由于它们已被删除重心分开，不会再同时出现在同一个子问题中，因此不会被重复统计。所以每条路径恰好被统计一次。

---

如果还有疑问，欢迎继续提出。

这是 deepseek 提供的点分治 + FFT 实现，但是我没空理解和修改，希望有神犇能修改一下码风。

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
int n;
vector<int> G[MAXN];
int siz[MAXN], del[MAXN], all, rtmx, rt;
long long ans[MAXN];

// ---------- FFT (必须用 vector<cd>) ----------
using cd = complex<double>;
const double PI = acos(-1.0);

void fft(vector<cd>& a, bool inv) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2.0 * PI / len * (inv ? -1.0 : 1.0);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1.0);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i + j], v = a[i + j + len / 2] * w;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w *= wlen;
            }
        }
    }
    if (inv) for (cd &x : a) x /= n;
}

vector<long long> convolution(const vector<int>& a, const vector<int>& b) {
    int need = (int)a.size() + (int)b.size() - 1;
    int n = 1;
    while (n < need) n <<= 1;
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(n); fb.resize(n);
    fft(fa, false); fft(fb, false);
    for (int i = 0; i < n; i++) fa[i] *= fb[i];
    fft(fa, true);
    vector<long long> res(need);
    for (int i = 0; i < need; i++) res[i] = llround(fa[i].real());
    return res;
}

// 添加距离数组 dists[0..m-1] 的贡献（sign = +1 或 -1）
void add_contrib(const int* dists, int m, int sign) {
    if (m < 2) return;
    int maxd = 0;
    for (int i = 0; i < m; i++) maxd = max(maxd, dists[i]);

    int* freq = new int[maxd + 1]();   // 初始化为0
    for (int i = 0; i < m; i++) freq[dists[i]]++;

    vector<int> freq_vec(freq, freq + maxd + 1);
    auto conv = convolution(freq_vec, freq_vec);

    long long* self = new long long[maxd * 2 + 1]();
    for (int d = 0; d <= maxd; d++)
        if (freq[d]) self[2 * d] += freq[d];

    int lim = min((int)conv.size(), n);
    for (int d = 1; d < lim; d++) {
        long long val = conv[d] - self[d];
        if (val & 1) val--;   // 防止浮点误差
        ans[d] += sign * (val / 2);
    }

    delete[] freq;
    delete[] self;
}

// ---------- 点分治（全部迭代） ----------
// 计算连通块大小和以每个节点为根的子树大小（同时记录父节点）
void getrt(int start) {
    static int parent[MAXN], order[MAXN];
    int top = 0;
    order[top++] = start;
    parent[start] = -1;
    for (int i = 0; i < top; i++) {
        int u = order[i];
        for (int v : G[u]) {
            if (v == parent[u] || del[v]) continue;
            parent[v] = u;
            order[top++] = v;
        }
    }
    // 逆序计算 size
    for (int i = top - 1; i >= 0; i--) {
        int u = order[i];
        siz[u] = 1;
        for (int v : G[u]) {
            if (v == parent[u] || del[v]) continue;
            if (parent[v] == u) siz[u] += siz[v];
        }
    }
    // 找重心
    int best = top + 1;
    rt = start;
    for (int i = 0; i < top; i++) {
        int u = order[i];
        int mx = top - siz[u];
        for (int v : G[u]) {
            if (v == parent[u] || del[v]) continue;
            if (parent[v] == u) mx = max(mx, siz[v]);
        }
        if (mx < best) {
            best = mx;
            rt = u;
        }
    }
}

// 收集从节点 u 出发（父为 p）的距离，填入 out 数组，返回数量
int getdis(int u, int p, int d0, int* out) {
    struct State { int u, p, d; };
    static State st[MAXN];
    int top = 0;
    st[top++] = {u, p, d0};
    int cnt = 0;
    while (top) {
        State cur = st[--top];
        out[cnt++] = cur.d;
        for (int v : G[cur.u]) {
            if (v == cur.p || del[v]) continue;
            st[top++] = {v, cur.u, cur.d + 1};
        }
    }
    return cnt;
}

void calc(int x) {
    // 分配一个足够大的数组存储所有距离
    int* all_dists = new int[MAXN];
    int total = 1;
    all_dists[0] = 0;   // 重心自身

    // 记录每个子树的起始位置和长度
    int starts[MAXN], lens[MAXN];
    int sub_cnt = 0;

    for (int y : G[x]) {
        if (del[y]) continue;
        int start = total;
        int len = getdis(y, x, 1, all_dists + start);
        starts[sub_cnt] = start;
        lens[sub_cnt] = len;
        sub_cnt++;
        total += len;
    }

    add_contrib(all_dists, total, +1);
    for (int i = 0; i < sub_cnt; i++) {
        add_contrib(all_dists + starts[i], lens[i], -1);
    }

    delete[] all_dists;
}

void divide(int x) {
    getrt(x);          // 计算重心并存入 rt
    int cen = rt;
    del[cen] = 1;
    calc(cen);

    for (int y : G[cen]) {
        if (!del[y]) {
            divide(y);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0, a, b; i < n - 1; i++) {
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    all = rtmx = n;
    divide(0);

    for (int i = 1; i < n; i++) {
        if (i > 1) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}