NC206091. 小王子
描述
“如果我沿着这条路一直往上面去，我就可以摘到那一颗星星。”
“可是物理好难啊。”
“那我还是去炸星星好了。”
“就算是要到月亮上去罚站也没关系呀。”
题目描述
十二月的风凌冽。
他站在阳台上，嘴里叼着一根从隔壁房间偷来的草莓味棒棒糖，眯着眼试图从漫天飞雪中嗅到一丝秋天的气息。黑与白构成不分明的界限，混沌地勾勒出陌生的形状。
倒像是一堆散乱的线条。
他又眯着眼看那清凌凌的夜空。
像是那么多的星星。
随手把剩下的棍子扔向，他打了个哈欠，想起厨房里的《赢在微点》。
再看，是N颗星星牵着N-1条线。
是N-1条白色的线束缚着N颗星星，将他们束缚成一个星团。
“你为什么盯着星星看这么久？”
“我喜欢一颗小星星，所以遥望星空，试图用大脑向宇宙发送一些信号。”
“那宇宙给你反馈了吗？”
“没呢。”
“希望那颗小星星可以在宇宙来临之前，先跑到我面前哦。”
“那就换一颗嘛，天上的星星多得是。”
——可那线条好少。
——那便多一点好了。
于是他依稀看见M条黑色的线与N-1条白色的线交错，不重合也不缠绕。都只是轻轻地拉着那些星星，并不捆绑，却不知怎的令他们无法脱身。
“宇宙给你反馈了吗？”
“没有。”
“那就换一颗嘛，天上的星星多得是。”
“环游整个星系，我大概找不到更亮的星星。”
——那就去摘啊。自己的星星自己摘。
——可是我的宇宙飞船可能会遇到流星，可能会用光所有的燃料。
——可是宇宙里的信号表示，那颗小星星在靠近。星河万顷，都是见面礼。
——可他有点慢啊。
——那就把他炸下来。
他看着那些不存在的线条与星星，决定用他仅有的两发导弹之中的一发去毁灭一条白线，使那些星星分成两部分。
想着他在物理书上写下：“#define 炸星星 使那些星星分成两部分”。
然后失望地发现有些时候无法成功地炸星星。
于是他决定用仅剩的一发他本决定用来保证晚年幸福的导弹去毁灭一条黑线。
不是每一个月亮都能遇到宇航员的。
但他还是想知道他有多少种使他的小星星在下一秒便出现在他怀里的方案。
可他要送什么见面礼给他的小星星呢？
他只有两发导弹、一本《赢在微点》、一本《普通高中课程标准实验教科书物理必修2》和一根草莓味棒棒糖。
草莓味棒棒糖已经被他吃完并丢弃了，而星星想必也不会喜欢物理书与物理教辅。
所以他决定就算一发导弹一条白线就能把他的小星星带到他面前，他也要再炸一条黑线给他的小星星。
也许这样会让他的爱与企盼再长大一点点吧。
至少看起来长大一点点。
顺便，把方案数也送给他的小星星。
星星被分成了两部分，那么下面的星星会下坠吧。
如果他们没有遇见像他一样的人，也许他们会遇见饥饿的小怪兽，小怪兽也许会嚼碎这些小星球。
“我就藏在漫天的星光里呀。”
他不怕外星人把他那些星星抢走的。
抢不走的.
输入描述
第一行包含两个整数N和M；
之后N-1行，每行包括两个整数X和Y，表示X和Y之间有一条白线；
之后M行，每行包括两个整数X和Y，表示X和Y之间有一条黑线。
输出描述
输出一个整数表示炸掉一条白线和黑线使得星星被分成两部分的方案数。
示例1
输入:
4 1 1 2 2 3 1 4 3 4
输出:
3
说明:
炸掉任意一组黑线和白线都能将星星分为两部分，3*1=3C++14(g++5.4) 解法, 执行用时: 290ms, 内存消耗: 21480K, 提交时间: 2020-06-06 18:45:32
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 600010
int n,m;
struct edge{int y,next;}e[maxn<<1];
int first[maxn],len=0;
void buildroad(int x,int y){e[++len]=(edge){y,first[x]};first[x]=len;}
int f[maxn][20],g[maxn],deep[maxn];
void dfs(int x,int fa,int dep)
{
f[x][0]=fa;deep[x]=dep;
for(int i=first[x];i;i=e[i].next)
if(e[i].y!=fa)dfs(e[i].y,x,dep+1);
}
int get_lca(int x,int y)
{
if(deep[x]>deep[y])swap(x,y);
for(int i=19;i>=0;i--)if(deep[f[y][i]]>=deep[x])y=f[y][i];
if(x!=y){for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];x=f[x][0];}
return x;
}
long long ans=0;
void get_ans(int x,int fa)
{
for(int i=first[x];i;i=e[i].next)
if(e[i].y!=fa)get_ans(e[i].y,x),g[x]+=g[e[i].y];
if(g[x]==1&&x!=1)ans++;
if(g[x]==0&&x!=1)ans+=m;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1,x,y;i<n;i++)scanf("%d %d",&x,&y),
buildroad(x,y),buildroad(y,x);dfs(1,0,1);
for(int j=1;j<=19;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
for(int i=1,x,y;i<=m;i++)
{
scanf("%d %d",&x,&y);
int lca=get_lca(x,y);
g[x]++,g[y]++;g[lca]-=2;
}
get_ans(1,0);printf("%lld",ans);
}
C++11(clang++ 3.9) 解法, 执行用时: 266ms, 内存消耗: 29584K, 提交时间: 2020-07-24 20:38:05
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const int N=2e5+5;
vector<int> v[N];
int fa[N][20],dep[N],sz[N],n,m,x,y;
ll ans=0;
void dfs(int x,int f){
dep[x]=dep[f]+1;
fa[x][0]=f;
for(int i=1;i<=18;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for(auto i:v[x]){
if(i==f) continue;
dfs(i,x);
}
}
void dfs2(int x,int f){
for(auto i:v[x]){
if(i==f) continue;
dfs2(i,x);
sz[x]+=sz[i];
if(sz[i]==0) ans+=m;
else if(sz[i]==1) ans++;
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=18;i>=0;i--){
if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
}
if(x==y) return x;
for(int i=18;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int main(){
std::ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
cin>>n>>m;
for(int i=1;i<n;i++){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,1);
for(int i=0;i<m;i++){
cin>>x>>y;
sz[x]++;
sz[y]++;
sz[lca(x,y)]-=2;
}
dfs2(1,1);
cout<<ans;
}