4543: [POI2014]Hotel加强版

链接

分析：

　　f[u][i]表示子树u内，距离u为i的点的个数，g[u][i]表示在子树u内，已经选了两个深度一样的点，还需要在距离u为i的一个点作为第三个点。

　　然后就可以利用这两个数组统计答案了。

　　ans+=g[u][j]*f[v][j-1]+f[u][j]*g[v][j+1];

　　如果直接合并f和g，复杂度是$O(n^2)$的，如果可以启发式合并，复杂度是$O(nlogn)$的，如果是长链剖分，复杂度是$O(n)$的。

　　长链剖分就是按照子树内最长的链就行剖分，根节点保留深度最大的那个点的信息，其他的点暴力合并。

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 #include<cctype>

 #include<set>

 #include<queue>

 #include<vector>

 #include<map>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 struct Edge{ int to, nxt; } e[N << ];

 int head[N], len[N], fa[N], son[N], En;

 LL ans, *f[N], *g[N], ft[N], gt[N << ], *fp = ft, *gp = gt;

 inline void add_edge(int u,int v) {

     ++En; e[En].to = v, e[En].nxt = head[u]; head[u] = En;

     ++En; e[En].to = u, e[En].nxt = head[v]; head[v] = En;

 }

 void dfs(int u) {

     len[u] = ;

     for (int i = head[u]; i; i = e[i].nxt) {

         int v = e[i].to;

         if (v == fa[u]) continue;

         fa[v] = u;

         dfs(v);

         if (len[v] +  > len[u]) len[u] = len[v] + , son[u] = v;

     }

 }

 void solve(int u) {

     f[u][] = ;

     if (!son[u]) return ;

     int v = son[u];

     g[v] = g[u] - ; f[v] = f[u] + ;

     solve(v);

     ans += g[u][];

     for (int i = head[u]; i; i = e[i].nxt) {

         v = e[i].to;

         if (v == fa[u] || v == son[u]) continue;

         g[v] = gp + len[v] + ; gp += (len[v] * );

         f[v] = fp + ; fp += len[v];

         solve(v);

         for (int j = ; j <= len[v]; ++j) {

             if (j) ans += g[u][j] * f[v][j - ];

             ans += f[u][j] * g[v][j + ];

             if (j) g[u][j] += f[u][j] * f[v][j - ];

             g[u][j] += g[v][j + ];

             if (j) f[u][j] += f[v][j - ];

         }

     }

 }

 int main() {

     int n = read();

     for (int i = ; i < n; ++i) {

         int u = read(), v = read();

         add_edge(u, v);

     }

     dfs();

     g[] = gp + len[] + ; gp += (len[] * );

     f[] = fp + ; fp += len[];

     solve();

     cout << ans;

     return ;

 }