显然和果树那题是一个套路。
这样的限制可以在 \(O(n \log n)\) 内全部找出，那么转化为矩形，求面积并即可。
但是这个时候发现我们矩形边界大概是 \(4n \log n\) 的规模，再快排无疑会浪费更多的时间。
正解居然是桶排！
而且人傻自带大常数必须 O3 才能艹过去。
代码： 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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
while(ch < '0' || ch > '9')
w |= ch == '-',ch = gc();
while(ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
w ? x = -x : x;
}
const int N = 1e5;
const int LG = 20;
int n;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
long long ans;
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v;
pre[tot] = first[u];
first[u] = tot;
}
struct node
{
int s,len;
} seg[(N << 2) + 10];
inline void up(int p,int tl,int tr)
{
if(seg[p].s)
seg[p].len = tr - tl + 1;
else if(tl == tr)
seg[p].len = 0;
else
seg[p].len = seg[ls].len + seg[rs].len;
}
void update(int l,int r,int k,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
{
seg[p].s += k;
up(p,tl,tr);
return ;
}
int mid = tl + tr >> 1;
if(l <= mid)
update(l,r,k,ls,tl,mid);
if(r > mid)
update(l,r,k,rs,mid + 1,tr);
if(!seg[p].s)
seg[p].len = seg[ls].len + seg[rs].len;
}
int id[N + 5],dep[N + 5],sz[N + 5],f[N + 5][LG + 5];
void dfs(int p)
{
static int tot = 0;
id[p] = ++tot,sz[p] = 1;
for(register int i = 1;i <= LG;++i)
f[p][i] = f[f[p][i - 1]][i - 1];
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ f[p][0])
dep[to[i]] = dep[p] + 1,f[to[i]][0] = p,dfs(to[i]),sz[p] += sz[to[i]];
}
struct edge
{
int x,y1,y2,k;
inline bool operator<(const edge &o) const
{
return x < o.x;
}
} e[(N << 7) + 10];
vector<edge> buc[N + 10];
int tot;
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
read(n);
int u,v;
for(register int i = 1;i < n;++i)
read(u),read(v),add(u,v),add(v,u);
dep[1] = 1,dfs(1);
for(register int i = 1,x,y,t;i <= n;++i)
for(register int j = 2;i * j <= n;++j)
{
x = i,y = i * j;
if((id[x] <= id[y] && id[y] < id[x] + sz[x]) || (id[y] <= id[x] && id[x] < id[y] + sz[y]))
{
if(dep[x] > dep[y])
swap(x,y);
t = y;
for(register int k = LG;~k;--k)
if(f[t][k] && dep[f[t][k]] > dep[x])
t = f[t][k];
if(id[t] > 1)
{
e[++tot] = (edge){1,id[y],id[y] + sz[y] - 1,1};
e[++tot] = (edge){id[t],id[y],id[y] + sz[y] - 1,-1};
e[++tot] = (edge){id[y],1,id[t] - 1,1};
e[++tot] = (edge){id[y] + sz[y],1,id[t] - 1,-1};
}
if(id[t] + sz[t] <= n)
{
e[++tot] = (edge){id[t] + sz[t],id[y],id[y] + sz[y] - 1,1};
e[++tot] = (edge){n + 1,id[y],id[y] + sz[y] - 1,-1};
e[++tot] = (edge){id[y],id[t] + sz[t],n,1};
e[++tot] = (edge){id[y] + sz[y],id[t] + sz[t],n,-1};
}
}
else
{
e[++tot] = (edge){id[x],id[y],id[y] + sz[y] - 1,1};
e[++tot] = (edge){id[x] + sz[x],id[y],id[y] + sz[y] - 1,-1};
e[++tot] = (edge){id[y],id[x],id[x] + sz[x] - 1,1};
e[++tot] = (edge){id[y] + sz[y],id[x],id[x] + sz[x] - 1,-1};
}
}
for(register int i = 1;i <= tot;++i)
buc[e[i].x].push_back(e[i]);
tot = 0;
for(register int i = 1;i <= n + 1;++i)
for(register int j = 0;j < buc[i].size();++j)
e[++tot] = buc[i][j];
for(register int i = 1;i <= tot;++i)
{
update(e[i].y1,e[i].y2,e[i].k,1,1,n);
if(i < tot)
ans += (long long)(e[i + 1].x - e[i].x) * seg[1].len;
}
printf("%lld\n",((long long)n * (n - 1) - ans) / 2);
}