「CodeForces 191C」Fools and Roads

发表于 |
字数统计: 561 | 阅读时长 ≈ 3

给一棵有根树和一些路线，路线上的边权都+1，求所有边的权值

链接

CodeForces 191C

题解

这个题目的输出是每一条边所经过的次数，所以想到树上边差分。
在差分之后确实是晕了，没有想到好的方法，但是突然想到了DFS求树上前缀和，对于每一条边，只要计算深度小的前缀和-深度大的前缀和即得答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct edge{
    ll to,prev;  
};
ll nc,ec,query,root,from,to;
ll depth[500010],anc[500010][31],last[500010],diff[500010],prefix[500010],LCA,maxn;
ll From[500010],To[500010];
edge ed[500010*2];
inline void addEdge(ll from,ll to)
{
    ed[++ec].prev=last[from];
    ed[ec].to=to;
    last[from]=ec;
}
inline void dfs(ll node)
{
    ll son;
    for(register int i=last[node];i!=0;i=ed[i].prev)
    {
        son=ed[i].to;
        if(!depth[son])
        {
            depth[son]=depth[node]+1;
            anc[son][0]=node;
            dfs(son);
        }
    }
}
inline void LCASetup()
{
    depth[1]=1;
    anc[1][0]=0;
    dfs(1);
    for(register int i=1;i<=21;i++)
    {
        for(register int j=1;j<=nc;j++)
        {
            anc[j][i]=anc[anc[j][i-1]][i-1];
        }
    }
}
inline ll lca(ll x,ll y)
{
    if(depth[x]>depth[y])
    {
        swap(x,y);
    }
    for(register int i=21;i>=0;i--)
    {
        if(depth[anc[y][i]]>=depth[x])
        {
            y=anc[y][i];
        }
    }
    if(x==y)
    {
        return x;
    }
    for(register int i=21;i>=0;i--)
    {
        if(anc[x][i]!=anc[y][i])
        {
            x=anc[x][i];
            y=anc[y][i];
        }
    }
    return anc[x][0];
}
inline void ddfs(ll node)
{
    for(register int i=last[node];i;i=ed[i].prev)
    {
        if(ed[i].to==anc[node][0])
        {
            continue;
        }
        ddfs(ed[i].to);
        diff[node]+=diff[ed[i].to];
    }
}
inline void dffs(ll node,ll val)
{
    prefix[node]=diff[node]+val;
    for(register int i=last[node];i;i=ed[i].prev)
    {
        if(ed[i].to==anc[node][0])
        {
            continue;
        }
        dffs(ed[i].to,prefix[node]);
    }
}
int main()
{
    scanf("%d",&nc);
    for(register int i=0;i<nc-1;i++)
    {
        scanf("%d%d",&from,&to);
        From[i]=from,To[i]=to;
        addEdge(from,to);
        addEdge(to,from);
    }
    LCASetup();
    scanf("%d",&query);
    for(register int i=0;i<query;i++)
    {
        scanf("%d%d",&from,&to);
        LCA=lca(from,to);
        diff[from]++,diff[to]++,diff[LCA]-=2;
    }
    ddfs(1);
    dffs(1,0);
    for(register int i=0;i<nc-1;i++)
    {
    	if(depth[From[i]]<depth[To[i]])
    	{
    		swap(From[i],To[i]);
        }
        printf("%d ",prefix[From[i]]-prefix[To[i]]);
    }
}