8.16集训

Posted on Edited on In

考试了呗 ### 酒店

click

观察题面可以得到：树上三个点之间的距离两两相同，说明距离一定是偶数，并且终点一定重合

考虑枚举中点，要求的就是三个点到中点距离相同的方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int N = 1e5+66;

int head[N], to[N], nex[N], cnt;

inline void add(int x, int y)
{
   to[++ cnt] = y;
   nex[cnt] = head[x];
   head[x] = cnt;
}

inline long long read() {
   long long s = 0, f = 1; char ch;
   while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
   for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
   return s * f;
}

int md, g[N], d[N];
LL f1[N], f2[N], f3[N];

inline void dfs(int x, int fa)
{
   int i, y;
   md = max(md, d[x]), ++ g[d[x]];
   for (i = head[x]; i; i = nex[i])
   {
      y = to[i];
      if (y == fa) continue;
      d[y] = d[x] + 1;
      dfs(y, x);
   }
}

inline LL query(int x, int n)
{
   int i, j, y; LL ans(0);
// memset(f1, 0, sizeof f1),memset(f2, 0, sizeof f2), memset(f3, 0, sizeof f3);
   for (i = head[x]; i; i = nex[i])
   {
      y = to[i];
      d[y] = md = 1, dfs(y, x);
      for (j = md; j >= 1; -- j)
      {
         f3[j] += (LL)f2[j]*g[j];
         f2[j] += (LL)f1[j]*g[j];
         f1[j] += (LL)g[j];
         g[j] = 0;
      }
   }
   for (i = 1; i <= n; ++ i) ans += f3[i];
   for ( i = 1; i <= md<<1; ++ i) f1[i] = f2[i] = f3[i] = 0; 
   for (i = 1; i <= n; ++ i) 
   return ans;
}

inline int thestars()
{
   int i, n, x, y;
   LL res(0);
   n = read();
   for (i = 1; i < n; ++ i)
   {
      x = read();
      y = read();
      add(x, y);
      add(y, x);
   }
   for (i = 1; i <= n; ++ i) res += query(i, n);
   cout << res;
   return 0;
}

int youngore = thestars();

signed main() {;}

最长道路tree

click

树的直径加并查集

把权值从大到小排序，按照顺序加点，维护每个联通块的最长链乘以当前点权值作为贡献

考虑在连上一条边之后，如何快速找到新的直径？

这里GXZ大佬给出了我们一个结论：将两棵树连成一棵，新树的直径的两端点只可能是原来两棵树里面两条直径四个端点中的某一个

要用并查集维护树的直径长度以及端点位置，倍增求LCA

开LL

PS：如果用LL全部替换掉int的话，大概率会T，我们只需要对查询函数以及答案开LL就可以了

还有，初始化的时候，尽量多初始化一点，但是也不要用memset，大概率会T

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e5+66;

int head[N], to[N], nex[N], cnt;

inline void add(int x, int y)
{
   to[++ cnt] = y;
   nex[cnt] = head[x];
   head[x] = cnt;
}

int v[N], d[N], f[N], id[N];
int fa[N][18], logs[N], px[N], py[N];
LL ans(0);

inline bool cmp(int a, int b) {return v[a] > v[b];}

inline int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}

inline void dfs(int x)
{
   int i, y;
   for (i = 1; (1 << i) <= d[x]; ++ i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
   for (i = head[x]; i; i = nex[i])
   {
      y = to[i];
      if (y == fa[x][0]) continue;
      fa[y][0] = x;
      d[y] = d[x] + 1;
      dfs(y);
   }
}

inline int lca(int x, int y)
{
   int i;
   if (d[x] < d[y]) swap(x, y);
   for (i = logs[d[x] - d[y]]; ~i; -- i)
      if (d[x] - d[y] >= (1 << i))
         x = fa[x][i];
   if (x == y) return x;
   for (i = logs[d[x]]; ~i; -- i)
      if (d[x] >= (1 << i) && fa[x][i] != fa[y][i])
         x = fa[x][i], y = fa[y][i];
   return fa[x][0];
}

inline int dis(int x, int y) {return d[x] + d[y] - (d[lca(x, y)] << 1);}

inline void solve(int x)
{
   int i, tx, ty, t, vm, vx, vy, y;
   for (i = head[x]; i; i = nex[i])
   {
      y = to[i];
      if (f[y])
      {
         tx = find(x), ty = find(y), vm = -1;
         if (vm < (t = dis(px[tx], py[tx]))) vm = t, vx = px[tx], vy = py[tx];      
         if (vm < (t = dis(px[ty], py[ty]))) vm = t, vx = px[ty], vy = py[ty];
         if (vm < (t = dis(px[tx], px[ty]))) vm = t, vx = px[tx], vy = px[ty];
         if (vm < (t = dis(px[tx], py[ty]))) vm = t, vx = px[tx], vy = py[ty];
         if (vm < (t = dis(py[tx], px[ty]))) vm = t, vx = py[tx], vy = px[ty];
         if (vm < (t = dis(py[tx], py[ty]))) vm = t, vx = py[tx], vy = py[ty];
         f[ty] = tx, px[tx] = vx, py[tx] = vy;
      }
   }
   tx = find(x);
   ans = max(ans, (LL)v[x] * (dis(px[tx], py[tx]) + 1));
}

inline int thestars()
{
   int i, x, y, n;
   cin >> n;
   for (i = 1; i <= n; ++ i) scanf ("%d", &v[i]), id[i] = i;
   for (i = 2; i <= n; ++ i)
   {
      scanf ("%d%d", &x, &y);
      add(x, y);
      add(y, x);
      logs[i] = logs[i >> 1] + 1;
   }
   dfs(1);
   sort(id + 1, id + n + 1, cmp);
   for (i = 1; i <= n; ++ i)
   {
      f[id[i]] = px[id[i]] = py[id[i]] = id[i];
      solve(id[i]);
   }
   cout << ans;
   return 0;
}

int youngore = thestars();

signed main() {;}

精神污染

click

不会！