文档章节

loj 10131 暗的连锁

o
 osc_wws45aot
发布于 2019/08/20 11:39
字数 1126
阅读 16
收藏 0
c++

精选30+云产品,助力企业轻松上云!>>>

题目

题目描述

原题来自:poj3417

Dark 是一张无向图,图中有 N个节点和两类边,一类边被称为主要边,而另一类被称为附加边。Dark 有N -1条主要边,并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。另外,Dark 还有 M 条附加边。

你的任务是把 Dark 斩为不连通的两部分。一开始 Dark 的附加边都处于无敌状态,你只能选择一条主要边切断。一旦你切断了一条主要边,Dark 就会进入防御模式,主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断 Dark 的一条附加边。

现在你想要知道,一共有多少种方案可以击败 Dark。注意,就算你第一步切断主要边之后就已经把 Dark 斩为两截,你也需要切断一条附加边才算击败了 Dark。

输入格式

第一行包含两个整数  N和 M

之后 N-1 行,每行包括两个整数 A 和 B,表示 A 和 B 之间有一条主要边;

之后 M 行以同样的格式给出附加边。

输出格式

输出一个整数表示答案。

样例

样例输入

4 1 
1 2 
2 3 
1 4 
3 4

样例输出

3

数据范围与提示

对于 20% 的数据1 <= N,M<=100

对于 100% 的数据1<=N<=105,1 <= M <= 2*105。数据保证答案不超过 231 - 1

分析

一本通(提高篇)P250

每一条附加边(u,v)都相当于把树上(u,v)路径上的所有边都“覆盖”了一遍,断其中一条边不会断树

统计出每一条边“覆盖”了几次,0次的直接断掉就会断树,任意断一条附加边即可,1次的断附加边的方案唯一,2次及以上无解

统计覆盖次数用到了树上差分,把边权下放到下面的点

差分学习资料:差分数组 and 树上差分 By 顾z

代码

  1 /**********************
  2 User:Mandy.H.Y
  3 Language:c++
  4 Problem:
  5 Algorithm:
  6 Date: 
  7 **********************/
  8 
  9 //LCA,树上差分 
 10 
 11 #include<bits/stdc++.h>
 12 #define Max(x,y) ((x) > (y) ? (x) : (y))
 13 #define Min(x,y) ((x) < (y) ? (x) : (y))
 14 
 15 using namespace std;
 16 
 17 const int maxn = 1e5 + 5;
 18 const int maxm = 2e5 + 5;
 19 
 20 int n,m,ans;
 21 int size,first[maxn],score[maxn];
 22 int top[maxn],cnt[maxn],father[maxn],dep[maxn];
 23 
 24 struct Edge{
 25     int v,nt;
 26 }edge[maxm];
 27 
 28 char *TT,*mo,but[(1 << 15) + 2];
 29 #define getchar() ((TT == mo && (mo = ((TT = but) + fread(but,1,1 << 15,stdin)),TT == mo)) ? -1 : *TT++)
 30 template<class T>inline void read(T &x){
 31     x = 0;bool flag = 0;char ch = getchar();
 32     while( ! isdigit(ch)) flag |= ch == '-',ch = getchar();
 33     while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
 34     if(flag) x = -x;
 35 }
 36 
 37 template<class T>inline void putch(const T x){
 38     if(x > 9) putch(x / 10);
 39     putchar(x % 10 | 48);
 40 }
 41 
 42 template<class T>inline void put(const T x){
 43     if(x < 0) putchar('-'),putch(-x);
 44     else putch(x);
 45 }
 46 
 47 void file(){
 48     freopen("yam2.in","r",stdin);
 49 //    freopen("network.out","w",stdout);
 50 }
 51 
 52 void eadd(int u,int v){
 53     edge[++ size].v = v;
 54     edge[size].nt = first[u];
 55     first[u] = size;
 56 }
 57 
 58 void readdata(){
 59     read(n);read(m);
 60     for(int i = 1;i < n; ++ i){
 61         int u,v;
 62         read(u);read(v);
 63         eadd(u,v);eadd(v,u);
 64     }
 65 }
 66 
 67 void dfs(int u,int f,int d){
 68     top[u] = u;dep[u] = d;
 69     int mcnt = 0,son = 0;
 70     father[u] = f;cnt[u] = 1;
 71     
 72     for(int i = first[u];i;i = edge[i].nt){
 73         int v = edge[i].v;
 74         if(v == f) continue;
 75         dfs(v,u,d + 1);
 76         cnt[u] += cnt[v];
 77         if(mcnt < cnt[v]){
 78             mcnt = cnt[v];
 79             son = v;
 80         }
 81     }
 82     
 83     if(son) top[son] = u;
 84 }
 85 
 86 int find(int u){
 87     return top[u] == u ? u : top[u] = find(top[u]);
 88 }
 89 
 90 int LCA(int x,int y){
 91     if(find(x) == find(y)) return dep[x] < dep[y] ? x : y;
 92     else return dep[top[x]] <dep[top[y]] ? LCA(x,father[top[y]]) : LCA(y,father[top[x]]);
 93     //没想到有一天模板也会打错 
 94 }
 95 
 96 void dfs1(int u){
 97     for(int i = first[u];i;i = edge[i].nt){
 98         int v = edge[i].v;
 99         
100         if(v == father[u]) continue;
101         
102         dfs1(v);
103         score[u] += score[v]; //累加 
104         if(score[v] == 0){
105             ans+=m;
106         } else if(score[v] == 1) ans++;
107     }
108 }
109 
110 void work(){
111     
112     dfs(1,0,0);
113     
114     for(int i = 1;i <= m; ++ i){
115         int u,v;
116         read(u);read(v);
117         int anc = LCA(u,v); 
118         score[u]++,score[v]++;
119         score[anc]-=2;
120         //差分
121         //把边下放到点 
122     }
123     
124     dfs1(1);
125 //    put(score[1]);puts("");
126     put(ans);
127 }
128 
129 int main(){
130 //    file();
131     readdata();
132     work();
133     return 0;
134 }
View Code

 

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Kotlin Class「T」

fun <T> gotoMainPage( context: Activity, postId: String, mainActivity: Class<T> ) { val intent = Intent(context, ADSplash......

osc_qatrfv06
12分钟前
0
0
小赢科技2020年一季报:由盈转亏1.96亿,M3以下贷款逾期率翻倍达6.71%

来源 | 新金融一线 北京时间6月29日,美股上市互金平台小赢科技公布了今年一季报未经审计的财务业绩报告。财报显示,该公司2020财年第一财季净营收同比下降31.9%至5.29亿元(人民币,下同);...

镭射财经
12分钟前
5
0
kotlin实现单例

/** * 功能:单例实现 */class Singleton private constructor() { companion object { val instance by lazy(mode = LazyThreadSafetyMode.SYNCHRONIZED) { Si......

osc_5nscij7v
12分钟前
7
0
七月算法机器学习 11 决策树、随机森林、 adaboost

目录 主要内容 决策树 信息增益 三种决策树学习算法 决策树的例子 决策树的过拟合 Bootstraping Bagging的策略 随机森林 提升的概念 Adaboost 举例 主要内容 决策树  决策树学习采用的是自...

osc_2718ydlo
14分钟前
10
0
支持千万人次毫秒级交易,360金融的系统性能如何做到?

提到“系统性能”问题,便立即联想到刚刚过去的“618”购物狂欢,电商公司在面对高密集度并发交易行为时,依托强大的系统性能以保持用户在网购与支付过程中平台的系统稳定性的极致案例。系统...

osc_jrhexi1r
15分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部