考虑常数优化
by 权御天下 @ 2018-08-26 20:22:15
@[lucky0218](/space/show?uid=30561)
一个log?
by shanjb0221 @ 2018-08-26 20:24:22
对啊，，把两个点搞到一个重链上，一个log啊
by lucky0218 @ 2018-08-26 20:40:34
为了巨佬看得清，我把他变好看了一点
```
#include<bits/stdc++.h>
using namespace std;
const int mx=1e6+3;
int son[mx],sz[mx],id[mx],tp[mx],f[mx],d[mx],n,del[mx],mson,cnt,k,maxn;
vector <int> a[mx];
void dfs1(int x,int fa,int deep){
d[x]=deep,f[x]=fa,sz[x]=1,mson=-11;
int l=a[x].size();
for (int i=0;i<l;i++){
int v=a[x][i];
if (v==fa) continue;
dfs1(v,x,deep+1);
sz[x]+=sz[v];
if (sz[v]>mson) mson=sz[v],son[x]=v;
}
}
void dfs2(int x,int tpf){
id[x]=++cnt;
tp[x]=tpf;
if (!son[x]) return;
dfs2(son[x],tpf);
int l=a[x].size();
for (int i=0;i<l;i++){
int v=a[x][i];
if (v==f[x]||v==son[x]) continue;
dfs2(v,v);
}
}
void update(int x,int y){
while (tp[x]!=tp[y]){
if (d[tp[x]]<d[tp[y]]) swap(x,y);
del[id[tp[x]]]++,del[id[x]+1]--;
x=f[tp[x]];
}
if (d[x]<d[y]) swap(x,y);
del[id[y]]++,del[id[x]+1]--;
}
int main(){
cin>>n>>k;
for (int i=1;i<n;i++){
int s,t;
scanf("%d%d",&s,&t);
a[s].push_back(t);
a[t].push_back(s);
}
dfs1(1,0,1);
dfs2(1,1);
for (int i=1;i<=k;i++){
int s,t;
scanf("%d%d",&s,&t);
update(s,t);
}
for (int i=1;i<=n+1;i++){
del[i]+=del[i-1];
}
for (int i=1;i<=n;i++)
maxn=max(maxn,del[i]);
cout<<maxn;
}
```
by 御·Dragon @ 2018-08-29 09:47:42
emmm
卡常大法好
~~（写树剖怎么能不卡常呢）~~
by yizimi远欣 @ 2018-10-31 20:32:46