[SDFZOJ]1069:树上统计

神题。。。std丑的不行。

我们可以发现i->i+1的边被覆盖过i×(n-i)次。

因为以1->i为左端点，以i+1->n的为右端点，i->i+1都将被覆盖这么多次。

然后从1->n扫，i->i+1的路径上的边的贡献就是n×(n-i)×边数-路径上的标记和×(n-i)。因为标记的意义就是它最后一次被覆盖是什么时候。如果tag是k，那么之前1->k为左端点就都统计过这个了。所以就要减标记和×(n-i)（由上面的话可知是n-i次），然后在路径上上打大小为i的tag。具体实现就是树剖+线段树。（我的树剖是直接粘的板子。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N=400005;
int n,m,r,a[N],head[N],ecnt,siz[N],fa[N],dep[N],son[N],dfn1[N],dfn2[N],top[N],ncnt,rnk[N]; 
struct Segtree {
    int sum,lazy,l,r;
} seg[N<<2];
struct Edge {
    int to,nxt;
} e[N<<1];
inline void pushup(int x) {
    seg[x].sum=seg[x<<1].sum+seg[x<<1|1].sum;

}
inline void add(int bg,int ed){
    e[++ecnt].nxt=head[bg];
    e[ecnt].to=ed;
    head[bg]=ecnt;
}
void build(int L,int R,int x) {
    seg[x].l=L,seg[x].r=R;
    if(L==R) {
        seg[x].sum=a[rnk[L]];
        return;
    }
    int mid=(L+R)>>1;
    build(L,mid,x<<1);
    build(mid+1,R,x<<1|1);
    pushup(x);
}

inline void pushdown(int x) {
    if(seg[x].lazy) {
        if(seg[x].l!=seg[x].r) {
            seg[x<<1].sum=seg[x].lazy*(seg[x<<1].r-seg[x<<1].l+1);

            seg[x<<1|1].sum=(seg[x].lazy)*(seg[x<<1|1].r-seg[x<<1|1].l+1);

            seg[x<<1].lazy=seg[x].lazy;

            seg[x<<1|1].lazy=seg[x].lazy;

        }
        seg[x].lazy=0;
    }
}
void update(int L,int R,int x,int c) {
    if(R<seg[x].l||L>seg[x].r)return;
    if(L<=seg[x].l&&seg[x].r<=R) {
        seg[x].lazy=c;
        seg[x].sum=(seg[x].r-seg[x].l+1)*c;

        return;
    }
    pushdown(x);
    update(L,R,x<<1,c);
    update(L,R,x<<1|1,c);
    pushup(x);
}
int query(int L,int R,int x){
    if(L>seg[x].r||R<seg[x].l)return 0;
    if(L<=seg[x].l&&seg[x].r<=R){
        return seg[x].sum;
    }
    pushdown(x);
    return (query(L,R,x<<1)+query(L,R,x<<1|1));
}
void dfs1(int x){
    siz[x]=1;
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(fa[x]==v) continue;
        fa[v]=x;
        dep[v]=dep[x]+1;
        dfs1(v);
        siz[x]+=siz[v];
        if(siz[v]>siz[son[x]]) son[x]=v;
    }
}
void dfs2(int x,int qtop){
    top[x]=qtop;dfn1[x]=++ncnt;
    rnk[dfn1[x]]=x;
    if(son[x]) dfs2(son[x],qtop);
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa[x]||v==son[x]) continue;
        dfs2(v,v);
    }
    dfn2[x]=ncnt;
}
void add_v(int x,int y,int z){
    int f1=top[x],f2=top[y];
    while(f1!=f2){
        if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);
        update(dfn1[f1],dfn1[x],1,z);
        x=fa[f1],f1=top[x];
    }
    if(dep[x]>dep[y]) update(dfn1[y],dfn1[x],1,z);
    else update(dfn1[x],dfn1[y],1,z);
}
inline int query_path(int x,int y){
    int f1=top[x],f2=top[y],ans=0;
    while(f1!=f2){
        if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);
        ans+=query(dfn1[f1],dfn1[x],1);
        x=fa[f1],f1=top[x];
    }
    if(dep[x]>dep[y]) ans+=query(dfn1[y],dfn1[x],1);
    else ans+=query(dfn1[x],dfn1[y],1);
    return ans;
}
inline int LCA(int x,int y){
        while(top[x]!=top[y])
            (dep[top[x]]>=dep[top[y]])? x=fa[top[x]]:y=fa[top[y]];;
        return dep[x]<dep[y]?x:y;
}
signed main() {
    cin>>n;
    int u,v,b,c;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs1(1);
    dfs2(1,1);
    build(1,n,1);
    long long ans=0;
    for(int i=1,lca;i<n;i++) {
        lca=LCA(i,i+1);
        ans+=(1ll*(dep[i]-dep[lca]+dep[i+1]-dep[lca])*(n-i)*i-1ll*(query_path(i,i+1)-query_path(lca,lca))*(n-i));
        int tp=query_path(lca,lca);
        add_v(i,i+1,i);add_v(lca,lca,tp);
    }
    cout<<ans<<endl;
    return 0;
}