林下风气
题目描述
里口福因有林下风气，带领全国各地高校掀起了一股 $AK$ 风，大家都十分痴迷于 $AK$。里口福为了打击大家的自信心，出了一道自以为十分困难的题目。
里口福有一棵树，第 $i$ 个节点上有点权 $a_i$，他的问题就是这棵树中有多少个不同的连通块满足连通块的最大值与最小值之差 $=k$，两个连通块不同当且仅当至少存在一个节点在一个连通块中出现而另一个连通块中没有出现。
痴迷于 $AK$的你马上接下这道题目，在里口福狂妄的笑声中，你切掉这道题的决心更加坚定了，现在就差你的代码了。
思路
$n<=333$，可以写一个暴力 $DP$。首先我们枚举联通块的最大值 / 最小值，对于每一对确定的值，令 $f_{i,0/1,0/1}$ 表示 $i$ 为当前联通块深度最小的点，有没有选到最大值 / 最小值，暴力转移即可。时间复杂度 $O(n^2)$，不过常数很大。
代码
#include <bits/stdc++.h>
#define mod 19260817
#define maun 4000
using namespace std;
struct Edge{
int to,neut;
Edge(int a=0,int b=0){
to=a,neut=b;
}
}l[maun<<1];
int head[maun];
long long f[maun][2][2];
int w[maun],cnt,n,k;
long long ans;
void Add(int a,int b){
l[++cnt]=Edge(b,head[a]);
head[a]=cnt;
}
void Dfs(int u,int fa,int L,int R){
if (w[u]==R&&L!=R) f[u][1][0]=1;
if (w[u]==L&&L!=R) f[u][0][1]=1;
if (w[u]==R&&L==R) f[u][1][1]=1;
if(w[u]>L&&w[u]<R) f[u][0][0]=1;
for (int i=head[u];i;i=l[i].neut){
int v=l[i].to;
if (v==fa) continue;
Dfs(v,u,L,R);
if (w[u]<L||w[u]>R) continue;
f[u][1][1]=(f[u][1][1]+f[u][1][1]*(f[v][1][0]+f[v][0][1]+f[v][0][0])+f[u][1][0]*f[v][0][1]+f[u][0][1]*f[v][1][0]+(f[u][0][0]+f[u][1][0]+f[u][0][1]+f[u][1][1])*f[v][1][1])%mod;
f[u][1][0]=(f[u][1][0]+f[u][1][0]*f[v][0][0]+f[u][0][0]*f[v][1][0]+f[u][1][0]*f[v][1][0])%mod;
f[u][0][1]=(f[u][0][1]+f[u][0][1]*f[v][0][0]+f[u][0][0]*f[v][0][1]+f[u][0][1]*f[v][0][1])%mod;
f[u][0][0]=(f[u][0][0]+f[u][0][0]*f[v][0][0])%mod;
}
(ans+=f[u][1][1])%=mod;
}
int main(){
freopen("lkf.in","r",stdin);
freopen("lkf.out","w",stdout);
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
scanf("%d",w+i);
for (int i=1,a,b;i<n;i++){
scanf("%d%d",&a,&b);
Add(a,b),Add(b,a);
}
for (int up=k;up<=n;up++){
int down=up-k;
Dfs(1,0,down,up);
memset(f,0,sizeof(f));
}
printf("%lld",(ans+mod)%mod);
}
盟主的忧虑
题目描述
江湖由 $N$ 个门派（$2≤N≤100,000$，编号从 $1$ 到 $N$）组成，这些门派之间有 $N-1$ 条小道将他们连接起来，每条道路都以“尺”为单位去计量，武林盟主发现任何两个门派都能够直接或者间接通过小道连接。
虽然整个江湖是可以互相到达的，但是他担心有心怀不轨之徒破坏这个武林的安定，破坏小道，于是武林盟主又秘密地修建了 $M$ 条密道（$1≤M≤100,000$），但每条小道距离都不超过10亿尺。
果不其然，最近一个名叫“太吾”的组织意欲破坏武林的小道，请你帮盟主想想办法，如果门派 $A$ 到门派 $B$ 的直连小道被破坏，从 $A$ 走到 $B$ 的所有路径中，经过密道的距离最少是多少？
思路
显然，破环一条小路将图分成了两部分，我们要寻找跨越这两部分的密道中最小的那条。显然，一条密道有作用当且仅当被破坏的小路在其两端门派的树上路径上。一个可行的做法是树链剖分求区间最小值。这里我们使用并查集解决这个问题，因为我的树剖调不出来一直爆零。
如何用并查集解决？对于一条密道 $(u,v,w)$，如果 $u$ 到 $v$ 的路径上的边中存在边之前还没有被覆盖过，那么说明这条边的答案就是 $w$.可以用并查集维护这条边有没有被覆盖，同时维护每个集合中深度最小的节点。对于密道 $(u,v,w)$，每次在 $u$ 所在集合中找到深度最小的点，这个点与父亲的连边一定就是上述没有被覆盖的边，将这条边的答案更新为 $w$，然后将这个节点与其父亲合并，直到 $u$ 所在集合的深度最小的节点变成了 $u$ 和 $v$ 的 $lca$。对 $v$ 做同样的过程即可。
这里我写了一个 $O(1)$ 的 LCA，其实并不需要。对于 $u,v$，在上述深度最小的节点向上跳的时候，同时按深度操作 $u,v$，就可以类似倍增地直接找到 $lca$。
代码
#include <bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define maxn 100010
#define inf INT_MAX
#define mid ((l+r)>>1)
#define chkmin(a,b) a=(a<b?a:b)
using namespace std;
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
}l[maxn<<1];
struct Node{
int l,r,val;
Node(int a=0,int b=0,int c=0){
l=a,r=b,val=c;
}
bool operator < (const Node &x) const{
return val<x.val;
}
}s[maxn];
struct ios{
inline char read(){
static const int IN_LEN=1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
}
template <typename _Tp> inline ios & operator >> (_Tp&x){
static char c11,boo;
for(c11=read(),boo=0;!isdigit(c11);c11=read()){
if(c11==-1)return *this;
boo|=c11=='-';
}
for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
boo&&(x=-x);
return *this;
}
}io;
int head[maxn],w[maxn],up[maxn],n,m,cnt,ind;
int fa[maxn],mind[maxn],dep[maxn],ans[maxn];
int lca[maxn<<2][19],dfn[maxn<<2],pos[maxn],path[maxn][2];
inline void Add(int a,int b){
l[++cnt]=Edge(b,head[a]);
head[a]=cnt;
}
inline void Dfs(int u,int f){
dep[u]=dep[f]+1;up[u]=f;
dfn[pos[u]=++ind]=u;
for (register int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==f) continue;
Dfs(v,u);
dfn[++ind]=u;
}
}
inline void Init(){
for (register int i=1;i<=ind;i++)
lca[i][0]=dfn[i];
for (register int j=1;j<20;j++)
for (register int i=1;i<=ind;i++){
if (i+(1<<j)-1<=ind){
if (dep[lca[i][j-1]]<dep[lca[i+(1<<(j-1))][j-1]])
lca[i][j]=lca[i][j-1];
else lca[i][j]=lca[i+(1<<(j-1))][j-1];
}
}
}
inline int getlca(int x,int y){
int l=pos[x],r=pos[y];
if (l>r) swap(l,r);
int k=log(r-l+1.0)/log(2.0);
if (dep[lca[l][k]]<dep[lca[r-(1<<k)+1][k]])
return lca[l][k];
return lca[r-(1<<k)+1][k];
}
inline int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
int fx=find(x),fy=find(y);
if (fx!=fy){
fa[fx]=fy;
int newmind;
if (dep[mind[fx]]<dep[mind[fy]])
newmind=mind[fx];else newmind=mind[fy];
mind[fx]=mind[fy]=newmind;
}
}
inline void explan(int x,int y,int k){
x=mind[x];
while(dep[up[x]]>=dep[y]){
ans[x]=min(ans[x],k);
merge(up[x],mind[x]);
x=mind[fa[x]];
}
}
int main(){
freopen("worry.in","r",stdin);
freopen("worry.out","w",stdout);
io>>n>>m;
for (register int i=1,a,b;i<n;i++){
io>>a>>b;
Add(a,b),Add(b,a);
path[i][0]=a,path[i][1]=b;
}
Dfs(1,0);Init();
fill(ans+1,ans+1+n,inf);
for (register int i=1;i<=n;i++)
fa[i]=i,mind[i]=i;
for (register int i=1,a,b,c;i<=m;i++){
io>>a>>b>>c;
s[i]=Node(a,b,c);
}
sort(s+1,s+1+m);
for (register int i=1;i<=m;i++){
int topf=getlca(s[i].l,s[i].r);
explan(s[i].l,topf,s[i].val);
explan(s[i].r,topf,s[i].val);
}
for (register int i=1;i<n;i++){
int ask=(dep[path[i][0]]>dep[path[i][1]]?path[i][0]:path[i][1]);
printf("%d\n",(ans[ask]==inf?-1:ans[ask]));
}
}