1 条题解

  • 0
    @ 2026-1-30 1:20:46
    #include <bits/stdc++.h>
    using namespace std;
    
    #define pb push_back
    #define vi vector<int>
    #define rd(x) scanf("%d", &x)
    #define print(x) printf("%lld\n", x)
    
    typedef long long ll;
    
    const int N = 1e5 + 7;
    int n, d[N], dep[N], son[N];
    vi e[N];
    ll *f[N], *g[N], p[N<<2], *o = p, ans;
    
    void dfs(int x, int fa) {
    	d[x] = d[fa] + 1;
    	for (auto y : e[x])
    		if (y != fa) {
    			dfs(y, x);
    			if (dep[y] > dep[son[x]]) son[x] = y;
    		}
    	dep[x] = dep[son[x]] + 1;
    }
    
    void dp(int x, int fa) {
    	if (son[x])
    		f[son[x]] = f[x] + 1, g[son[x]] = g[x] - 1, dp(son[x], x);
    	f[x][0] = 1, ans += g[x][0];
    	for (auto y : e[x])
    		if (y != fa && y != son[x]) {
    			f[y] = o, o += dep[y] << 1, g[y] = o, o += dep[y] << 1;
    			dp(y, x);
    			for (int i = 0; i < dep[y]; i++) {
    				if (i) ans += f[x][i-1] * g[y][i];
    				ans += g[x][i+1] * f[y][i];
    			}
    			for (int i = 0; i < dep[y]; i++) {
    				g[x][i+1] += f[x][i+1] * f[y][i];
    				if (i) g[x][i-1] += g[y][i];
    				f[x][i+1] += f[y][i];
    			}
    		}
    }
    
    int main() {
    	rd(n);
    	for (int i = 1, x, y; i < n; i++)
    		rd(x), rd(y), e[x].pb(y), e[y].pb(x);
    	dfs(1, 0), f[1] = o, o += dep[1] << 1, g[1] = o, o += dep[1] << 1;
    	dp(1, 0), print(ans);
    	return 0;
    }
    
    • 1

    D34_3「POI2014 R1」酒店 Hotels 加强版

    信息

    ID
    6208
    时间
    1000ms
    内存
    500MiB
    难度
    9
    标签
    递交数
    11
    已通过
    3
    上传者