A. 闹市

  • 在树上做差分， 求lca 最后再跑一遍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
    const int N = 1e6+10;
    int n,k;
    struct{
    	int to,nex;
    }edge[N<<1];
    int head[N<<1],edge_num;
    inline void add(int x,int y){
    	edge[++edge_num].to = y;
    	edge[edge_num].nex = head[x];
    	head[x] = edge_num;
    }
    int fa[N][25],dep[N];
    inline void dfs(int now,int fu){
    	fa[now][0] = fu;
    	dep[now] = dep[fu]+1;
    	for(int i=1;(1<<i)<=dep[now];++i) fa[now][i] = fa[fa[now][i-1]][i-1];
    	for(int i=head[now];i;i=edge[i].nex){
    		int tto = edge[i].to;
    		if(tto==fu) continue;
    		dfs(tto,now);
    	}
    }
    inline int lca(int x,int y){
    	if(dep[x]>dep[y]) swap(x,y);
    	for(int i=24;i>=0;--i){
    		if(dep[fa[y][i]]>=dep[x]) y=fa[y][i];
    	}
    	if(x==y) return x;
    	for(int i=24;i>=0;--i){
    		if(fa[y][i]!=fa[x][i]){
    			y = fa[y][i];
    			x = fa[x][i];
    		}
    	}
    	return fa[x][0];
    }
    int tmp[N],ans;
    inline void dfs1(int now,int fu){
    	for(int i=head[now];i;i=edge[i].nex){
    		int tto = edge[i].to;
    		if(tto==fu) continue;
    		dfs1(tto,now);
    		tmp[now] += tmp[tto];
    	}
    	ans = max(ans,tmp[now]);
    }
    int main(){      
    	read(n,k);
    	for(int i=1,u,v;i<n;++i){
    		read(v,u);
    		add(u,v);
    		add(v,u);
    	}
    	dfs(1,0);
    	for(int i=1,u,v;i<=k;++i){
    		read(u,v);
    		tmp[u]++;tmp[v]++;tmp[lca(u,v)]--;tmp[fa[lca(u,v)][0]]--;
    	}
    	dfs1(1,0);
    	printf("%d",ans);

    	fclose(stdin);
    	fclose(stdout);
    	return 0;
    }

B. 王子

  • 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
    using namespace std;
    const int N=2e5+5;
    int n,m,a[N],cnt[N],sz[N],ans[N];
    vector<int> E[N];
    vector<pair<int,int> > q[N];
    void dfs(int u,int d,int f){
        for(auto x:q[u]) ans[x.first]=cnt[d+x.second+1];
        sz[u]=a[u];
        for(auto v:E[u]) if(v!=f) dfs(v,d+1,u),sz[u]+=sz[v];
        cnt[d]+=sz[u];
        for(auto x:q[u]) ans[x.first]+=sz[u]-cnt[d+x.second+1];
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",a+i);
        for(int i=2;i<=n;i++){
            int u;scanf("%d",&u);
            E[u].push_back(i);E[i].push_back(u);
        }
        for(int i=1;i<=m;i++){
            int x,h;scanf("%d%d",&x,&h);
            q[x].push_back({i,h});
        }
        dfs(1,0,0);
        for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    }

C. 逃跑

  • 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
    #define int long long
    using namespace std;
    const int N = 2e5+5;
    int n,m,dis[N],sum[N],fa[N],tot;
    pair<int,int>s[N];
    vector<pair<int,int> >g[N];
    void dsy(int u){
    	s[++tot]={dis[u],u};
    	sum[u]++;
    	auto tmp=lower_bound(s+1,s+1+tot,make_pair(dis[u]-m,0ll));
    	sum[fa[tmp->second]]--;
    	for(auto i : g[u]){
    		int v=i.first,w=i.second;
    		dis[v]=dis[u]+w;
    		fa[v]=u;
    		dsy(v);
    	}
    	tot--;
    }
    void ysd(int u){
    	for(auto  i : g[u]){
    		int v=i.first;
    		ysd(v);
    		sum[u]+=sum[v];
    	}
    }
    signed main(){
    	cin>>n>>m;
    	for(int i = 2;i <= n;i++){
    		int u,v;
    		cin>>u>>v;
    		g[u].push_back(make_pair(i,v)); 
    	} 
    	dsy(1);
    	ysd(1);
    	for(int i = 1;i <= n;i++)cout<<sum[i]<<'\n';
    	return 0;
    }

D. 树上最多不相交路径

  • 按照LCA深度贪心选取
  • 满分的贪心，考虑一个性质：两条路径的相交，一定是某一条路径的lca在另一条路径上。

选择一条路径之后，它的lca对应的子树中的其他点，是不能在通过lca走向其他的点。

优先选取lca深度最大的点。这样影响的路径最少。

选取一条路径之后，把它lca内的所有节点都标记掉，表示不可以在使用。一个点如果已经被标记了，就不用在继续往下标记了。这样每个点，只会被标记一次。

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
const int N=2e5+10;
typedef pair<int,int> PII;
int dfn[N],top[N],sz[N],son[N],fa[N],dep[N],seq[N],ts;
vector<int> e[N];
bool st[N];
int w[N];
int n,m;

void dfs(int u,int p)
{
	fa[u]=p,dep[u]=dep[p]+1,sz[u]=1;
	for(auto v:e[u])
	{
		if(v==p) continue;
		dfs(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}

void Dfs(int u,int t)
{
	top[u]=t,dfn[u]=++ts,seq[ts]=u;
	if(son[u]) Dfs(son[u],t);
	for(auto v:e[u])
	{
		if(v==fa[u] || v==son[u]) continue;
		Dfs(v,v);	
	} 
}

int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		u=fa[top[u]]; 
	}
	if(dep[u]<dep[v]) swap(u,v);
	return v;
}

struct Data
{
	int u,v,p;
	bool operator<(const Data &t)const
	{
		return dep[p]>dep[t.p];
	}
}q[N];

void mark(int u)
{
	st[u]=true;
	for(auto v:e[u])
	{
		if(v==fa[u]) continue;
		if(st[v]) continue;
		mark(v);
	}
}

signed main()
{
	freopen("paths.in","r",stdin);
	freopen("paths.out","w",stdout);
	
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	
	cin>>n>>m;
	
	for(int i=1,a,b;i<n;i++)
	{
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	
	dfs(1,0);
	Dfs(1,1);
	
	for(int i=1;i<=m;i++) cin>>q[i].u>>q[i].v,q[i].p=lca(q[i].u,q[i].v);
	
	sort(q+1,q+1+m);
	
	int cnt=0;
	for(int i=1;i<=m;i++)
	{
		if(st[q[i].u] || st[q[i].v]) continue;
		cnt++;
		mark(q[i].p);
	}
	
	cout<<cnt<<"\n";
	
	return 0;
}