题目其实很简单，如果知道树上差分是什么基本就是秒了。
首先题面所说的，有\(n-1\)条边，保证两点之间只有一条简单路径，显然是树。
剩下的边就是让这个树产生环的非树边。题面要求删除两条边，使之分为两部分，假如没有环状的结构，也就是没有那些非树边，就只需要随便删除一条边就可以达成要求。题面要求这两条边必须是一条树上的边和非树边。其实就已经挺明显的了，我们对每一个非树边，让这个非树边所链接的两个点对应的树上的简单路径上的边全部+1，到最后，如果某一个边只被覆盖了一次，那么切断他就一定能够找到其它的非树边，使得这两个边被切断能够达成题目要求。
所以只需要对每个非树边，把他们对应的树上的边全部\(+1\)，最后再统计所有只被覆盖过一次，或者一次都没被覆盖的树边即可。
树上差分也是比较简单的，就是对于一个简单路径，如果要给他们之间的简单路径\(+1\)，就是给这两个节点\(+1\)，然后给他们的lca\(-2\)，
统计的时候就是直接统计对于每个节点的子树的权值和\(F[x]\)，这就是这个点和它父亲节点之间的树边上的值。
然后就没了。
为什么re
为什么。
我找不到错啊啊啊啊啊啊啊啊
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <string.h>
#define ll long long
using namespace std;
inline ll read(){
ll a=0,b=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
return a*b;
}
struct edge
{
ll next,to;
}e1[400001];
ll head1[400001],tot1,tot2;
ll dep[400001][22],f[400001][22],val[400001];
ll n,m;
inline void add1(ll i,ll j)
{
e1[++tot1].next=head1[i];
e1[tot1].to=j;
head1[i]=tot1;
}
void dfs(ll x,ll fa,ll now)
{
dep[x][0]=now-1;f[x][0]=fa;
for(ll i=head1[x];i!=0;i=e1[i].next)
{
ll u=e1[i].to;
if(u==fa)continue;
dfs(u,x,now+1);
}
}
inline ll ask_lca(ll x,ll y)
{
if(dep[x][0]<dep[y][0])swap(x,y);
ll now=19;
while(now>=0)
{
if(dep[x][now]>dep[y][0])x=f[x][now];
now--;
}
now=19;
if(x==y)return x;
while(now>=0)
{
if(f[x][now]!=f[y][now])x=f[x][now],y=f[y][now];
now--;
}
return f[x][0];
}
ll F[400001];
ll ans=0;
void count(ll x,ll fa)
{
F[x]+=val[x];
for(ll i=head1[x];i!=0;i=e1[i].next)
{
ll u=e1[i].to;
if(u==fa)continue;
count(u,x);
F[x]+=F[u];
}
}
int main()
{
n=read();m=read();
for(ll i=1;i<n;i++)
{
ll x=read(),y=read();
add1(x,y);add1(y,x);
}
dfs(1,0,1);
for(ll i=0;i<=18;i++)
{
for(ll j=1;j<=n;j++)
{
f[j][i+1]=f[f[j][i]][i];
dep[j][i+1]=dep[f[j][i]][i];
}
}
for(ll i=1;i<=m;i++)
{
ll x=read(),y=read();
val[x]++;val[y]++;
val[ask_lca(x,y)]-=2;
}
count(1,0);
for(ll i=2;i<=n;i++)
{
if(F[i]>1)continue;
if(F[i]==1)
ans++;
else
ans+=m;
}
cout<<ans<<endl;
return 0;
}
毁灭吧。
标签：include,read,poj3417,ll,非树边,树上,now From： https://www.cnblogs.com/HLZZPawa/p/18301007