BZOJ4543: [POI2014] 호텔 강화판 긴 체인 해부

나무 한 그루를 주고 몇 개의 삼원조가 두 개의 거리를 충족시키는지 물었다.n<=100000 긴 체인 분할 응용의 하나: o(n) 통계는 깊이를 아래로 표시한 합병 가능한 트리 정보가 현재 노드에 있음을 나타낸다. f(i)는 상대적인 깊이가 i인 노드 개수를 나타내고 g(i)는 트리 밖에서 현재 점과 거리가 i인 점은 트리 안의 몇 대점과 답안을 구성할 수 있음을 나타낸다.매번 새로운 아들이 올 때마다 길이를 매거하고 현재 g와 아들 f, 그리고 현재 f와 아들 g로 답안을 갱신한 다음에 양쪽 f로 g를 갱신하고 아들의 f와 g를 현재 f와 g로 밀어넣는다.순서 문제에 주의하다.처음에 장아들의 정보를 직접 계승했다. f수조는 전체 오른쪽으로 한 자리(바늘 왼쪽으로 한 자리), g수조는 전체 오른쪽으로 한 자리이다.반드시 상속할 때도 이 점을 고려해야 한다. 자신과 장아들이 있는 자수 안에 구성된 답안수(즉 상속된 g[0])는 dfs할 때 모든 긴 체인 밑에 긴 체인 길이의 메모리를 분배한다. g지침은 매번 오른쪽으로 이동하고 오른쪽으로 렌을 옮긴 후에 렌의 공간이 필요하기 때문에 2*len을 분배해야 한다.이 문제를 o(n)로 해결할 수 있다.

#include
#define gm 100005
using namespace std;
typedef long long ll;
inline ll* __alloc(size_t size)
{
    static ll pool[gm<<2];
    static ll* ptr=pool;
    ll* res=ptr;ptr+=size;
    return res;
}
struct e
{
    int t;
    e *n;
    e(int t,e *n):t(t),n(n){}
}*p[gm];
int dep[gm],son[gm],len[gm],fa[gm];
ll *F[gm],*G[gm];
void dfs(int x)
{
    son[x]=x;
    for(e *i=p[x];i;i=i->n)
    {
        if(i->t==fa[x]) continue;
        fa[i->t]=x;
        dep[i->t]=dep[x]+1;
        dfs(i->t);
        if(dep[son[i->t]]>dep[son[x]]) son[x]=son[i->t];
    }
    len[x]=dep[son[x]]-dep[x]+1;
    for(e *i=p[x];i;i=i->n)
    {
        if(i->t==fa[x]) continue;
        if(son[i->t]!=son[x])
        {
            int y=son[i->t];
            F[y]=__alloc(len[i->t])+len[i->t]-1;
            G[y]=__alloc(len[i->t]<<1);
        }
    }
    if(x==1)
    {
        int y=son[x];
        F[y]=__alloc(len[x])+len[x]-1;
        G[y]=__alloc(len[x]<<1);
    }
}
ll ans=0;
void DP(int x)
{
    ll *&f=F[x],*&g=G[x];
    for(e *i=p[x];i;i=i->n)
    {
        if(i->t==fa[x]) continue;
        DP(i->t);
        if(son[x]==son[i->t])
        {
            f=F[i->t]-1;
            g=G[i->t]+1;
        }
    }
    ans+=g[0];
    ++f[0];
    for(e *i=p[x];i;i=i->n)
    {
        if(i->t==fa[x]||son[i->t]==son[x]) continue;
        ll *fs=F[i->t],*gs=G[i->t];
        ans+=fs[0]*g[1];
        for(int w=1;wt];++w)
            ans+=fs[w]*g[w+1]+gs[w]*f[w-1];
        g[1]+=fs[0]*f[1];
        f[1]+=fs[0];
        for(int w=1;wt];++w)
        {
            g[w+1]+=fs[w]*f[w+1];
            g[w-1]+=gs[w];
            f[w+1]+=fs[w];
        }
    }
}
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;iint u,v;
        scanf("%d%d",&u,&v);
        p[u]=new e(v,p[u]);
        p[v]=new e(u,p[v]);
    }
    dfs(1);
    DP(1);
    printf("%lld
",ans);
    return 0;
}