UVa1674 Lightning Energy Report

这道题应该是迄今为止我做的时间跨度最久的题，在2018.5.17第一次提交，直到今天（2019.1.26）才终于AC。

题意就是给你一棵树，起初所有节点上的数是 $0$ ，对于每次操作 $(a,b,c)$ ，把 $a$ 和 $b$ 及之间的节点全部加上 $c$ ，最后输出每个节点上的数。

其实题本身很简单，就是一道裸的树剖，但是有多组数据，所以一定要记得清空数组！！！

需要被清空的数组：

前向星的边和头 $edge[],head[]$
线段树的值和lazy $sum[],delta[]$
树剖重儿子数组 $son[]$

2可以在建树时清空，我就是被3坑了大半年。

清空的变量就是前向星的 $cnt$ 和树剖中的dfs序变量 $dfsord$ ，这个没啥好说的。

顺便吐槽一下UVa上加了system("pause")都能过。

struct Edge{
    int next,to;
} edge[100005];
struct Tree{
    int left,right,sum,delta;
} tree[200005];
int deep[100005],top[100005],fa[100005],son[100005],id[100005],siz[100005],head[100005];
int n,m,a,b,c,t,cnt,dfsord,kase;

inline void init()
{
    cnt=0;
    dfsord=0;
    memset(head,0,sizeof(head));
    memset(edge,0,sizeof(edge));
    memset(son,0,sizeof(son));
}

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void pushup(int x)
{
    tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;
}

inline void pushdown(int x)
{
    tree[x*2].sum+=tree[x].delta*(tree[x*2].right-tree[x*2].left);
    tree[x*2+1].sum+=tree[x].delta*(tree[x*2+1].right-tree[x*2+1].left);
    tree[x*2].delta+=tree[x].delta;
    tree[x*2+1].delta+=tree[x].delta;
    tree[x].delta=0;
}

void build(int x,int l,int r)
{
    tree[x].left=l;
    tree[x].right=r;
    tree[x].sum=tree[x].delta=0;
    if (r-l>1)
    {
        build(x*2,l,(l+r)/2);
        build(x*2+1,(l+r)/2,r);
    }
}

void change(int x,int l,int r,int delta)
{
    if (l<=tree[x].left && r>=tree[x].right)
    {
        tree[x].sum+=delta*(tree[x].right-tree[x].left);
        tree[x].delta+=delta;
    }
    else
    {
        if (tree[x].delta) pushdown(x);
        int mid=(tree[x].left+tree[x].right)/2;
        if (l<mid) change(x*2,l,r,delta);
        if (r>mid) change(x*2+1,l,r,delta);
        pushup(x);
    }
}

int query(int x,int l,int r)
{
    if (l<=tree[x].left && r>=tree[x].right) return tree[x].sum;
    else
    {
        if (tree[x].delta) pushdown(x);
        int ans=0,mid=(tree[x].left+tree[x].right)/2;
        if (l<mid) ans+=query(x*2,l,r);
        if (r>mid) ans+=query(x*2+1,l,r);;
        return ans;
    }
}

void dfs1(int x,int f,int dep)
{
    deep[x]=dep;
    fa[x]=f;
    siz[x]=1;
    int mx=-1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs1(y,x,dep+1);
        siz[x]+=siz[y];
        if (siz[y]>mx) mx=siz[y],son[x]=y;
    }
}

void dfs2(int x,int topf)
{
    top[x]=topf;
    id[x]=++dfsord;
    if (!son[x]) return;
    dfs2(son[x],topf);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa[x] || y==son[x]) continue;
        dfs2(y,y);
    }
}

inline void uprange(int u,int v,int delta)
{
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        change(1,id[top[u]],id[u]+1,delta);
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    change(1,id[u],id[v]+1,delta);
}

inline int qrange(int u,int v)
{
    return query(1,id[u],id[v]+1);
}

int main()
{
    t=read();
    while (t--)
    {
        init();
        n=read();
        for (int i=1;i<n;i++)
        {
            a=read()+1; b=read()+1;
            add(a,b); add(b,a);
        }
        dfs1(1,0,1);
        dfs2(1,1);
        build(1,1,n+1);
        m=read();
        for (int i=1;i<=m;i++)
        {
            a=read()+1; b=read()+1; c=read();
            uprange(a,b,c);
        }
        printf("Case #%d:\n",++kase);
        for (int i=1;i<=n;i++) printf("%d\n",qrange(i,i));
    }
    return 0;
}

新评论