小王子「CSP多校联考 2019」

题意

又是一位被(oi)耽误了的文学家，甚至有一种做(lxl)题的感觉。

给定一棵树，向上加若干新边。现在可以删除一条树边一条新边，求将这棵树截断的方案数。

---

思路

• 对于一条边，如果没有新边覆盖他，显然删除这条边再删除任意一条新边均可。

• 如果有一条新边覆盖，那么删除这条树边再删除这条新边，只有一种方法。

• 否则不可能。

先把边转换为点然后跑一个树上差分即可。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

    template<typename T>inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }

    template<typename T>inline void write (T x) {
        if (x<0) putchar('-'),x*=-1;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }

}

using namespace StandardIO;

namespace Project {
	#define int long long
	
	const int N=200200;
	
	int n,m,ans;
	int cnt;
	int head[N];
	struct node {
		int to,next;
	} edge[N<<1];
	int f[N][22],dep[N];
	int g[N];
	
	inline void add (int a,int b) {
		edge[++cnt].to=b,edge[cnt].next=head[a],head[a]=cnt;
	}
	void init (int now,int fa) {
		dep[now]=dep[fa]+1,f[now][0]=fa;
		for (register int i=1; i<=21; ++i) {
			f[now][i]=f[f[now][i-1]][i-1];
		}
		for (register int i=head[now]; i; i=edge[i].next) {
			int to=edge[i].to;
			if (to==fa) continue;
			init(to,now);
		}
	}
	inline int lca (int x,int y) {
		if (dep[x]<dep[y]) swap(x,y);
		for (register int i=21; i>=0; --i) {
			if (dep[x]>=dep[y]+(1<<i)) x=f[x][i];
		}
		if (x==y) return x;
		for (register int i=21; i>=0; --i) {
			if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
		}
		return f[x][0];
	}
	void dfs (int now,int fa) {
		for (register int i=head[now]; i; i=edge[i].next) {
			int to=edge[i].to;
			if (to==fa) continue;
			dfs(to,now);
			g[now]+=g[to];
		}
	}

	inline void MAIN () {
		read(n),read(m);
		for (register int i=1,x,y; i<n; ++i) {
			read(x),read(y);
			add(x,y),add(y,x);
		}
		init(1,0);
		for (register int i=1,x,y; i<=m; ++i) {
			read(x),read(y);
			++g[x],++g[y],g[lca(x,y)]-=2;
		}
		dfs(1,0);
		for (register int i=2; i<=n; ++i) {
			if (g[i]==0) ans+=m;
			else if (g[i]==1) ++ans;
		}
		write(ans);
	}
	
	#undef int
}

int main () {
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    Project::MAIN();
}