JZOJ 100019 A

显然和果树那题是一个套路。

这样的限制可以在 O(nlogn) 内全部找出，那么转化为矩形，求面积并即可。

但是这个时候发现我们矩形边界大概是 4nlogn 的规模，再快排无疑会浪费更多的时间。
正解居然是桶排！

而且人傻自带大常数必须 O3 才能艹过去。

代码：

#pragma GCC optimize (3)
#include <cstdio>
#include <vector>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
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);
}