USACO 2019 January Contest Platinum: T1

题目大意

奶牛Bessie意识到为了保持好的体形她需要更多地进行锻炼。她需要你帮助她选择在农场里每天用来晨跑的路线。 农场由N块草地组成(1≤N≤2*10^5),方便起见编号为1…N,由M条双向的小路连接(1≤M≤2*10^5)。作为一种遵循规律的生物,奶牛们倾向于使用其中特定的N−1条小路作为她们日常在草地之间移动的路线——她们管这些叫“常规的”小路。从每块草地出发都可以仅通过常规的小路到达所有其他草地。

为了使她的晨跑更加有趣,Bessie觉得她应该选择一条包含一些非常规的小路的路线。然而,使用常规的小路能够使她感到舒适,所以她不是很想在她的路线中使用过多非常规的小路。经过一些思考,她认为一条好的路线应当形成一个简单环(能够不经过任何草地超过一次的情况下回到起点),其中包含恰好两条非常规的小路。

请帮助Bessie计算她可以使用的好的路线的数量。两条路线被认为是相同的,如果它们包含的小路的集合相等。

题目分析

考虑什么时候,两条 非常规边 可以在树上组成一个简单环。

假设这条两边分别为 (u1​,v1​), (u2​,v2​) ,观察发现,在树上以 u1​,v1 (非常规边与树构成的环)​为起止点的路径与以 u2​,v2​ 为起止点的路径有公共边的时候,那么就可以组成一个简单环。

 

那么原题题意就变成了给你一些树上的路径,求这些路径之间有多少对有边交.

首先,树上的路径是从 u -> lca -> v 这种形式的. 这并不利于我们操作。所以我们可以把每条路径拆成两个: u -> lca 与 v -> lca.

虽然这样会有一些重复计算,但是重复计算的部分很好剔除.

不难发现只有当两条路径的 lca 相同, 且两条路径与 lca 相连的两条边是一样的,这时才会重复计算。

举个例子(借用PhantasmDragon大佬的一张图)

USACO 2019 January Contest Platinum: T1

 

红、蓝两条路径拆开后,四条拆出来的链两两相交,这样答案会计算两次,这样我们只用-1就行。

方法就是对于每条路径都记录一下这两条与 lca 相连的边,放在一个 map 里就行了。

 

考虑如何计数,对于处理树上区间,我们当然可以使用树剖,但对于此题,有一种更简单的类似于“差分”的方法。

 

先考虑要是一条直线求覆盖,我们要怎么搞?

为了防止重复,对于一个线段 x ,我们只数与它相交,且 Li​>Lx​ 的线段 i.

这样就有一个简单做法. 对于每个线段 x, 在 Lx​ 时把答案减去满足 Li​<Lx​ 的 i 的个数,在 Rx​ 时把答案加上满足 Li​<Rx​ 的 i 的个数.

这样对于每个线段我们都算出了与它相交,且 Li​>Lx​ 的线段 i 的个数.

实现方法如上文所说,类似差分, 在每个 Li​ 位置 +1, 做一次前缀和, sum[Rx​]−sum[Lx​−1] 就是 线段 x 的答案.

*注意当有 L 相等的情况时,会重复计算,需要减去多算的.

 

那么,我们在树上做的事情也是完全一样的. 为了方便,我们把连接 x 与它父亲的边的权值放在 x 上。

对于一条拆分后的"简单"路径 (u,v)[depu​<depv​], 给这条路径上深度最浅的边 (u,uson​) 的权值+1,(放在 w[uson​]上) 然后做一次树上的前缀和, 那么这条路径的答案就是 sum[v]-sum[u]。

 

可以这样理解: 一个拆分后的路径的最浅边相当于一维模型中的 Lx​ , 最深边相当于 Rx​, 那么 Lx​−1 即为路径中最浅边上面的边, 即连接最高点 uu与其父亲的边.

注意一下最浅边重合的情况, 即 L 相等的情况, 处理方式和一维无差别.

 

 1 #include<bits/stdc++.h>
 2 #define Pii pair<int,int>
 3 #define MK make_pair
 4 using namespace std;
 5 typedef long long ll;
 6 const int MAXN=4e5+10;
 7 
 8 inline int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
11     while(ch>='0'&&ch<='9'){x=x*10+(ch-48);ch=getchar();}
12     return x*f;
13 }
14 struct Edge{
15     int to,nxt;
16 }e[MAXN<<1];
17 int cnt,head[MAXN];
18 inline void add_edge(int u,int v){
19     e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
20 } 
21 ll ans;
22 int n,m;
23 int f[MAXN][25],dep[MAXN];
24 int lca[MAXN];
25 int T[MAXN],num[MAXN];
26 Pii Node[MAXN];
27 map<Pii,int> Tp;
28 
29 inline void dfs1(int x){
30     for(int i=1;i<=20;++i)
31         f[x][i]=f[f[x][i-1]][i-1];
32     dep[x]=dep[f[x][0]]+1;
33     for(int i=head[x],y;i;i=e[i].nxt){
34         y=e[i].to;
35         if(y==f[x][0]) continue;
36         f[y][0]=x;
37         dfs1(y);
38     }
39 }
40 inline int Get_lca(int x,int y){
41     if(dep[x]<dep[y]) swap(x,y);
42     for(int i=20;i>=0;--i)
43         if(dep[f[x][i]]>=dep[y])
44             x=f[x][i];
45     if(x==y) return x;
46     for(int i=20;i>=0;--i)
47         if(f[x][i]!=f[y][i]){
48             x=f[x][i];
49             y=f[y][i];
50         }
51     return f[x][0];
52 }
53 inline int Get_top(int bot,int top){
54     if(bot==top) return -10;
55     for(int i=20;i>=0;--i)
56         if(dep[f[bot][i]]>dep[top])
57             bot=f[bot][i];
58     return bot;
59 } 
60 
61 inline void dfs2(int x,int cur_cnt){
62     num[x]=cur_cnt;
63     for(int i=head[x],y;i;i=e[i].nxt){
64         y=e[i].to;
65         if(y!=f[x][0])
66             dfs2(y,cur_cnt+T[y]);
67     }
68 }
69 int main(){
70     n=read();m=read();
71     for(int i=1,u,v;i<n;++i){
72         u=read();v=read();
73         add_edge(u,v);add_edge(v,u);
74     }
75     dfs1(1);
76     for(int i=1,u,v;i<=(m-(n-1));++i){
77         u=Node[i].first=read();
78         v=Node[i].second=read();
79         lca[i]=Get_lca(u,v);
80         
81         int uu=Get_top(u,lca[i]);//拆分后路径上最“浅”的点
82         int vv=Get_top(v,lca[i]);
83         if(uu!=-10){ans-=T[uu]+1;++T[uu];}//先减去"L相等时"重复计算的
84         if(vv!=-10){ans-=T[vv]+1;++T[vv];}
85         if(uu!=-10&&vv!=-10){
86             if(uu>vv) swap(uu,vv);
87             ans-=Tp[MK(uu,vv)]; //减去"两条路径的 lca 相同, 且两条路径与 lca 相连的两条边是一样的" 的环重复计算的个数
88             Tp[MK(uu,vv)]++;
89         }
90     }
91     dfs2(1,0);
92     for(int i=1;i<=(m-(n-1));++i)
93         ans+=(ll)(num[Node[i].first]+num[Node[i].second]-2*num[lca[i]]);
94     cout<<ans<<endl;
95     return 0; 
96 }

 

上一篇:Cable TV Network


下一篇:USACO 2018 December Contest Platinum T3: The Cow Gathering