[JLOI2014]松鼠的新家

题目描述

松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。

松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，......，最后到an，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不听地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。

维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。

因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

输入输出格式

输入格式：

第一行一个整数n，表示房间个数第二行n个整数，依次描述a1-an接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。

输出格式：

一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。

输入输出样例

输入样例#1：

输出样例#1：

说明

2<= n <=300000

一道水题，可是题目没看清，居然调了近一个小时，难受极了！！！

用tarjan求完LCA之后用差分进行操作，求出每条边被走过的次数，然后就可以通过跟每个点连接的边被走过的次数求出每个点被走过了次数，然后把最后一次减去就好了（不要忘记除以二！）

#include<cstdio>
#define ll long long
#define maxn 300300 << 1
using namespace std;

ll head_edge[maxn],head_quest[maxn],tot_edge,tot_quest,n,m,u,v,last;
ll cf[maxn],deep[maxn],zou[maxn],f[maxn],ans[maxn],fat[maxn],rans[maxn];

struct st{
    ll v,next;
}s[maxn];

struct que{
    ll u,v,lca,next;
    que *es;
}quest[maxn];

inline ll find(ll x)
{
    if(x == f[x]) return x;
    f[x] = find(f[x]);
    return f[x];
}

inline void add_quest(ll u,ll v)
{
    tot_quest++;
    if(tot_quest & 1) quest[tot_quest].es = &quest[tot_quest + 1];
    else quest[tot_quest].es = &quest[tot_quest - 1];
    quest[tot_quest].u = u;
    quest[tot_quest].v = v;
    quest[tot_quest].next = head_quest[u];
    head_quest[u] = tot_quest;
}

inline void add_edge(ll u,ll v)
{
    tot_edge++;
    s[tot_edge].v = v;
    s[tot_edge].next = head_edge[u];
    head_edge[u] = tot_edge;
}

inline void lca_tarjan(ll fa,ll now)
{
    for(ll i=head_edge[now];i;i=s[i].next)
        if(s[i].v != fa)
        {
            fat[s[i].v] = now;
            lca_tarjan(now,s[i].v);
        }
    for(ll i=head_quest[now];i;i=quest[i].next)
        if(zou[quest[i].v])
        {
            quest[i].lca = find(quest[i].v);
            quest[i].es -> lca = quest[i].lca;
        }
    zou[now] = 1;
    f[now] = fa;
}

inline ll dfs(ll fa,ll now)
{
    ll val = cf[now];
    for(ll i=head_edge[now];i;i=s[i].next)
        if(fa != s[i].v)
            val += dfs(now,s[i].v);
    ans[now] = val;
    return val;
}

int main(){
    scanf("%lld",&n);
    scanf("%lld",&u);
    for(ll i=1;i<n;i++)
    {
        scanf("%lld",&v);
        add_quest(u,v);
        add_quest(v,u);
        u = v;
    }
    for(ll i=1;i<n;i++)
    {
        scanf("%lld%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    for(ll i=1;i<=n;i++) f[i] = i;
    lca_tarjan(0,1);
    
    for(ll i=1;i<n;i++)
        quest[i] = quest[i * 2 - 1];
    
    for(ll i=1;i<n;i++)
    {
        cf[quest[i].u]++;
        cf[quest[i].v]++;
        cf[quest[i].lca] -= 2;
    }
    dfs(0,1);
    for(ll i=1;i<=n;i++)
    {
        rans[i] += ans[i];
        for(ll j=head_edge[i];j;j=s[j].next)
            if(s[j].v != fat[i])
                rans[i] += ans[s[j].v];
    }
    
    rans[quest[n - 1].v]--;
    for(ll i=1;i<=n;i++) printf("%lld
",rans[i] + 1 >> 1);
}