2021.7.17 Contest 题解
T1:
Description:
白云列出了一个方程：
(x^2 − 2Bx + C = 0)
白兔给出了一个区间 ([L,R])，要求参数 (C) 必须在这个区间内。
白云想知道，有多少组满足要求的正整数 ((B,C)) 使得这个方程有整数解。
Input:
第一行数据组数 (T)。
接下来 (T) 行每行两个数 (L,R) 。
Output:
对于每个询问输出答案。
Sample1 Input:
2
1 5
2 10
Sample1 Output:
4
7
Hint:
data range:
对于 (30\%) 的数据，(R le 1000)。
对于 (60\%) 的数据，(R le 10^6)。
对于 (100\%) 的数据，(1 le L le R le 10^{12},T le 10) 。
sample explaination:
第一问，合法的为 ((1,1),(2,3),(2,4),(3,5))。
第二问，合法的为 ((2,3),(2,4),(3,5),(4,7),(3,8),(3,9),(5,9))。
题目分析：
稍微转变一下题意，就是让我们求 ((B^2-C)) 为完全平方数的 ((B,C)) 二元组。
令 (B^2-C=P^2) ，则 ((B+P)*(B-P)=C)，由于 (C in [L,R])，所以 ((B-P) in [0,sqrt{C}])，不妨枚举 ((B-P))，就能求出所有合法的 (C)，于是这道题就结束了。
但是我写的不是这个方法。我们考虑满足 ((B+P)*(B-P)=C) 的 ((B,P)) 二元整数组一定是这样构造的：
令 (C=X*Y) ，则 (B=frac{X+Y}{2})，也就是说对于每一个 (C) 求出它拆分成两个约数相乘，且两个约数奇偶性相同的方案。
若 (C) 为奇数，则 (X,Y) 一定都是奇数，于是对于奇数只需要求出约数个数和即可；
若 (C) 为 (2) 的倍数且不为 (4) 的倍数，则 (X,Y) 必为一奇一偶，不符合条件；
若 (C) 为 (4) 的倍数，则不妨令 (frac{C}{4}=frac{X}{2}*frac{Y}{2})，问题转化为 (frac{C}{4}) 的约数个数和；
稍微用一些容斥的技巧，跑一遍数论分块即可。
代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int T;LL L,R; inline LL calc(LL n){
LL res=0;for(register LL i=1,j;i<=n;i=j+1) j=n/(n/i),res+=(n/i)*((((((j&1ll)?j:(j-1))-((i&1ll)?i:(i+1)))>>1ll)+1ll)-(((j-(j&1ll)-(i+(i&1ll)))>>1ll)+1ll)+((j-(j%4ll)-((i%4ll)?(i+4ll-i%4ll):i))/4ll+1ll));
res+=(sqrt(n)+1ll)/2ll,res>>=1ll;LL res2=0;n/=4ll;for(register LL i=1,j;i<=n;i=j+1) j=n/(n/i),res2+=(j-i+1ll)*(n/i);res2+=sqrt(n),res2>>=1ll;return res+res2;
}
struct FastIO{
static const int S=1048576;
char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
template<typename T>FastIO& operator >> (T&ret){
ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
}
FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
template<typename T>FastIO& operator << (T x){
if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
}
FastIO& operator << (char ch){pc(ch);return *this;}
FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
fin>>T;while(T--) fin>>L>>R,cout<<calc(R)-calc(L-1)<<'
';return 0;
}
T2:
Description:
白云有一个长度为 (n) 的序列 (a_1,...,a_n)。
白兔想找到这个序列的一些非空子序列。因为这些子序列多达 (2^n −1) 个，所以它只 需要字典序最小的 (k) 个。
两个序列的字典序的比较方式为：如果一个序列是另一个的前缀，则长度小的序列字典序小，否则找到两个序列从前往后第一个不同的元素，这个元素小的序列字典序小。
为了避免大量输出，对于每一个子序列你只需要输出它的哈希值。一个序列 (b_1,...,b_m) 的哈希值为 (sum_{i=1}^mb_iseed^{m-i}mod p)。
Input:
第一行四个数 (n,k,seed,p)。
第二行 (n) 个数表示这个序列。
Output:
输出 (k) 行，表示前 (k) 小的子序列的哈希值
Sample1 Input:
2 3 1 5
1 2
Sample1 Output:
1
3
2
Sample2 Input:
3 4 2 3
1 3 1
Sample2 Output:
1
1
0
2
Sample3 Input:
5 6 23 1000
1 2 4 2 3
Sample3 Output:
1
25
25
577
274
578
Hint:
data range:
对于 (20\%) 的数据，(nle15)。
对于 (30\%) 的数据，(nle2000)。
对于 (40\%) 的数据，(nle10^4)。
对于 (60\%) 的数据，(1le a_ile30)。
对于 (100\%) 的数据，(1le n,k,a_ile 10^5,1le seed,ple 10^6,kle 2^n-1)。
题目分析：
由于 (k) 比较小，我们考虑通过搜索直接从小到大地找出每个子序列。
首先我们找到全局最小值，然后用 (vector) 记录下所有全局最小值的位置，然后以第一个位置+1为起点往下递归，每两层递归之间用 two-pointers 扫一遍 (vector) 来算出以每个数字结尾有多少贡献，对于每一层都开一个 (vector) 存储。
回溯的时候把最小值删除求剩余的次小值，这个过程可以用主席树实现，但是我太懒了，于是写了个 (set) + (st表) 实现了一个复杂度显然不正确但是很难被卡掉的算法。
代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define N 200005
#define LL long long
#define s_id set<int>::iterator
#define inf 2147483647
using namespace std;
int n,K,top,seed,p,tot,tmp=1,a[N],ST[N][20],pw[N],P[20];vector<int> g[N],G[N];set<int> T[N];
inline int get(int x,int y){int len=log2(y-x+1);if(a[ST[x][len]]<=a[ST[y-P[len]+1][len]]) return ST[x][len];return ST[y-P[len]+1][len];}
inline void solve(int H){
int TMP=tmp,s=G[TMP][0];if(s==n) return;int x=a[get(s+1,n)],ss=G[TMP].size(),sum=0;H=1ll*H*seed%p,T[TMP].insert(G[TMP][0]),T[TMP].insert(n+1);while(sum<n-s){
int S=g[x].size(),now=0;for(register int i=0;i<S;i++) if(g[x][i]>s){
int pos=g[x][i];T[TMP].insert(pos),sum++;while(now<ss&&G[TMP][now]<pos) now++;now--;
for(register int j=0;j<=now;j++){K--,cout<<(H+x)%p<<'
';if(!K) exit(0);G[tmp+1].push_back(pos);}
}
if(G[tmp+1].size()) tmp++,solve((H+x)%p);int y=inf;for(s_id it=T[TMP].begin();it!=T[TMP].end();it++){int posx=*it+1;if(posx==n+2) break;s_id itt=it;itt++;int posy=*itt-1;if(posx<=posy){int tt=a[get(posx,posy)];y=min(y,tt);}}x=y;
}
}
struct FastIO{
static const int S=1048576;
char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
template<typename T>FastIO& operator >> (T&ret){
ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
}
FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
template<typename T>FastIO& operator << (T x){
if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
}
FastIO& operator << (char ch){pc(ch);return *this;}
FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
fin>>n>>K>>seed>>p,pw[0]=1;for(register int i=1;i<=n;i++) pw[i]=1ll*pw[i-1]*seed%p;P[0]=1;for(register int i=1;i<=16;i++) P[i]=P[i-1]*2;
for(register int i=1;i<=n;i++) fin>>a[i],g[a[i]].push_back(i),ST[i][0]=i;
for(register int i=1;i<=16;i++) for(register int j=1;j<=n-P[i]+1;j++) if(a[ST[j][i-1]]<=a[ST[j+P[i-1]][i-1]]) ST[j][i]=ST[j][i-1];else ST[j][i]=ST[j+P[i-1]][i-1];G[1].push_back(0),solve(0);return 0;
}
T3:
Description:
白云和白兔想占领一棵树。
白云列举了游戏玩法：
首先，白云任意选择一个结点 (k)，把这个结点占领，其它结点都未被占领。
每一轮，白云可以选择若干个已经被占领的点，然后分别从每个点出发，找一条出边，把到达的结点占领。
当所有结点都被占领时游戏结束。
白兔想知道，选择一个最优的 (k)，白云最少几轮可以完成游戏。
接下来白云和白兔想一起玩游戏，规则是这样：
一开始，白云选择了 (a) 号点，白兔选择了 (b) 号点，这两个结点都被占领，其它点都未被占领。
每一轮，白兔可以选择若干个已经被占领的点，然后分别从每个点出发，找任意一条出边，把到达的结点占领。
当所有结点都被占领时游戏结束。
白兔还想知道，最小多少轮可以占领所有结点？注意，这个游戏的 (a) 和 (b) 是固定的。
Input:
第一行三个数 (n,a,b)。
接下来 (n-1) 行每行两个数表示这棵树。
Output:
输出两行，第一行是第一个游戏的答案，第二行是第二个游戏的答案。
Sample1 Input:
6 2 1
1 2
2 3
2 4
1 5
5 6
Sample1 Output:
3
2
Hint:
对于 (30\%) 的数据，(n le 100)；
对于 (100\%) 的数据，(n le 10^5, a, b in [1, n], a e b)
题目分析：
第一个游戏一眼看去就是个换根DP套路题，注意换根的时候用前后缀优化，不然复杂度会退化成 (O(n^2))。
第二个游戏看起来有浓浓的二分性。我们二分在 (a) 到 (b) 的路径上断开某一条边，分别以 (a) 和 (b) 为根跑一遍树形DP，如果 (a) 需要的轮数比 (b) 多，就把断开的那条边向 (a) 的方向移动；反之向 (b) 的方向移动。
由于函数单调，正确性显然。
代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define N 300005
#define LL long long
#define inf 2147483647
using namespace std;
int n,a,b,tot,ans=inf,g[N],rk[N],A[N],f[N],F[N],W[N],fir[N],nxt[N<<1],son[N<<1],pre[N],suf[N],B[N];
inline void add(int x,int y){son[++tot]=y,nxt[tot]=fir[x],fir[x]=tot;} inline bool cmp(int x,int y){return x>y;} inline void dfs(int x,int fa){
for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa) dfs(son[i],x);tot=0;for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa) A[++tot]=f[son[i]];
sort(A+1,A+tot+1,cmp);for(register int i=1;i<=tot;i++) f[x]=max(f[x],A[i]+i);
}
inline void dfs2(int x,int fa,int X){
tot=0,A[++tot]=X;for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa) A[++tot]=f[son[i]];
sort(A+1,A+tot+1,cmp);for(register int i=1;i<=tot;i++) pre[i]=max(pre[i-1],i+A[i]),(A[i]>=0)&&(rk[A[i]]=i,0);suf[tot+1]=-n;for(register int i=tot;i;i--) suf[i]=max(suf[i+1],i-1+A[i]);
ans=min(ans,pre[tot]);for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa){int to=son[i],tmp=max(suf[rk[f[to]]+1],pre[rk[f[to]]-1]);g[to]=tmp;}
for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa) dfs2(son[i],x,g[son[i]]);
}
inline void DFS(int x,int fa){for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa) W[son[i]]=i,F[son[i]]=x,DFS(son[i],x);}
inline void check(int x,int fa,int id){
for(register int i=fir[x];i;i=nxt[i]) if((son[i]^fa)&&(i^id)&&((i^1)^id)) check(son[i],x,id);tot=0;for(register int i=fir[x];i;i=nxt[i]) if((son[i]^fa)&&(i^id)&&((i^1)^id)) A[++tot]=f[son[i]];
sort(A+1,A+tot+1,cmp),f[x]=0;for(register int i=1;i<=tot;i++) f[x]=max(f[x],A[i]+i);
}
struct FastIO{
static const int S=1048576;
char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
template<typename T>FastIO& operator >> (T&ret){
ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
}
FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
template<typename T>FastIO& operator << (T x){
if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
}
FastIO& operator << (char ch){pc(ch);return *this;}
FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
fin>>n>>a>>b,tot=1;for(register int i=1,x,y;i<n;i++) fin>>x>>y,add(x,y),add(y,x);dfs(1,0),ans=f[1],dfs2(1,0,-n);cout<<ans<<'
';
DFS(a,0);int x=b,res=0;while(x^a) B[++res]=W[x],x=F[x];int l=1,r=res;ans=inf;while(l<=r){int mid=l+r>>1;check(a,0,B[mid]),check(b,0,B[mid]);ans=min(ans,max(f[a],f[b]));if(f[a]>=f[b]) l=mid+1;else r=mid-1;}
cout<<ans<<'
';return 0;
}
T4:
Description:
特别提醒：本题时间限制只有 5.0s。
内鬼同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线,完成打卡任务。这个游戏的地图可以看作一一棵包含 (n) 个结点和 (n-1) 条边的树，每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 (1) 到 (n) 的连续正整数。
现在有 (m) 个玩家，第 (i) 个玩家的起点为 (s_i)，终点为 (t_i)。每天打卡任务开始时，所有玩家在第 (0) 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树，所以每个人的路径是唯一的)
内鬼想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 (j) 的观察员会选择在第 (w_j) 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 (w_j) 秒也正好到达了结点 (j) 。内鬼想知道每个观察员会观察到多少人?注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一 段时间后再被观察员观察到。 即对于把结点 (j) 作为终点的玩家：若他在第 (w_j) 秒前到达终点,则在结点 (j) 的观察员不能观察到该玩家；若他正好在第 (w_j) 秒到达终点,则在结点 (j) 的观察员可以观察到这个
爪巴者内鬼。 ——《P1600 [NOIP2016 提高组 ] 天天爱跑步》
但是这个游戏是在是太难了，所以游戏还增加了氪金的功能，具体来说，某人使用了钞能力之后，可以对地图上的边进行修改，删除边 ((a,b))，并添加边 ((c,d))，同时，为了维持服务器正常运行，保证地图仍然是一棵树。随着树形态的变化，内鬼 为了更全面地了解活跃度，决定在某些时刻修改某个 (W_j)。
Input:
输入第一行包含两个正整数 (n,m)，其中 (n) 代表结点的数量，同时也是观察员的数量，(m) 代表事件的数量。
接下来 (n−1) 行，每行两个数 (a,b)，描述这棵树。 接下来一行 (n) 个数，表示每个观察员的初始 (W) 值。
接下来 (m) 行，每行描述一个事件，有三种形式:
1 a b: 表示新的一天开始了，有一个玩家在时刻 (0) 从 (a) 沿最短路径跑到 (b)。
2 a b c d: 表示某人投了币，把边 ((a,b)) 替换为了边 ((c,d))。保证 ((a,b)) 边存在，并且替换结束后仍然是一棵树。
3 a b: 表示内鬼决定把 (a) 号观察员的 (W) 修改为 (b)。
Output:
输出仅包含 (1) 行 (n) 个数，第 (j) 个整数表示结点 (j) 的观察员可以观察到多少人。
Sample1 Input:
6 5
2 3
1 2
1 4
4 5
5 6
1 2 5 1 2 3
2 6 5 6 4
3 1 0
1 1 5
1 1 3
1 2 6
Sample1 Output:
2 0 0 1 1 1
Hint:
对于 (20\%) 的数据无操作 (2、3)。
对于另 (20\%) 的数据无操作 (2)。
对于另 (20\%) 的数据无操作 (3)。
对于另 (20\%) 的数据所有玩家经过的路径总长 (le 10^8)。
对于 (100\%) 的数据 (n,m le 10^5)。
题目分析：
考场上看到这道题就知道是道大毒瘤数据结构题。于是我们开始扣部分分。
无操作 (2、3) 就是天天爱跑步原题，直接上线段树合并；(事实上其实不需要线段树合并，可以用 (LCA) + 树上差分来实现)
路径总长 (leq 10^8) 直接拉一棵 (LCT) 来暴力维护；
由于博主太菜了，暂时没有想到第 (2,3) 个数据点怎么艹，欢迎大家踊跃留言告诉我。
正解：考虑分块。我们将询问分块，设块长为 (sqrt{n}) ，每 (sqrt{n}) 次操作之后直接暴力重构，块内操作考虑加入未删除的边，原来的一棵树就变成了一棵森林，而森林的总大小为 (n)，对于森林重新 dfs 一遍扫答案，同时注意 (W_i) 的更新以及 (a) 到 (b) 的实际路径，实现难度很高。
最终复杂度 (O(nsqrt{n} logn))，虽然常数巨大但是能把暴力艹掉
20分代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define s_id vector<int>::iterator
#define N 200005
using namespace std;
int tim,n,m,tot,tott,size,C[N],D[N],op[N],ans[N],sum[N*100],sum2[N*100],son[N*100][2],son2[N*100][2],rt[N],rt2[N],dep[N],fir[N],nxt[N<<1],to[N<<1],w[N],f[N][20],s[N],t[N];vector<int> g;
inline void add(int x,int y){to[++tot]=y,nxt[tot]=fir[x],fir[x]=tot;}
inline void dfs(int x){
dep[x]=dep[f[x][0]]+1;for(register int i=1;i<=18;i++) f[x][i]=f[f[x][i-1]][i-1];
for(register int i=fir[x];i;i=nxt[i])
if(to[i]!=f[x][0]) f[to[i]][0]=x,dfs(to[i]);
}
inline int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);for(register int i=18;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;for(register int i=18;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];
}
inline void modify(int &now,int l,int r,int x,int v){
if(!now) now=++tot;if(l==r){sum[now]+=v;return;}
int mid=l+r>>1;if(mid>=x) modify(son[now][0],l,mid,x,v);
else modify(son[now][1],mid+1,r,x,v);sum[now]=sum[son[now][0]]+sum[son[now][1]];
}
inline void merge(int &now,int last,int l,int r){
if(!now){now=last;return;}else sum[now]+=sum[last];if(l==r) return;
int mid=l+r>>1;if(son[last][0]) merge(son[now][0],son[last][0],l,mid);
if(son[last][1]) merge(son[now][1],son[last][1],mid+1,r);
}
inline void modify2(int &now,int l,int r,int x,int v){
if(!now) now=++tott;if(l==r){sum2[now]+=v;return;}
int mid=l+r>>1;if(mid>=x) modify2(son2[now][0],l,mid,x,v);
else modify2(son2[now][1],mid+1,r,x,v);sum2[now]=sum2[son2[now][0]]+sum2[son2[now][1]];
}
inline void merge2(int &now,int last,int l,int r){
if(!now){now=last;return;}else sum2[now]+=sum2[last];if(l==r) return;
int mid=l+r>>1;if(son2[last][0]) merge2(son2[now][0],son2[last][0],l,mid);
if(son2[last][1]) merge2(son2[now][1],son2[last][1],mid+1,r);
}
inline int query(int now,int l,int r,int x){
if(l==r) return sum[now];if(!now) return 0;
int mid=l+r>>1;if(mid>=x) return query(son[now][0],l,mid,x);
return query(son[now][1],mid+1,r,x);
}
inline int query2(int now,int l,int r,int x){
if(l==r) return sum2[now];if(!now) return 0;
int mid=l+r>>1;if(mid>=x) return query2(son2[now][0],l,mid,x);
return query2(son2[now][1],mid+1,r,x);
}
inline void dfs2(int x){
for(register int i=fir[x];i;i=nxt[i])
if(to[i]!=f[x][0]) dfs2(to[i]),merge(rt[x],rt[to[i]],1,size),merge2(rt2[x],rt2[to[i]],1,size);
int xx=lower_bound(g.begin(),g.end(),dep[x]+w[x])-g.begin()+1;
int yy=lower_bound(g.begin(),g.end(),dep[x]-w[x])-g.begin()+1;
ans[x]=query(rt[x],1,size,xx)+query2(rt2[x],1,size,yy);
}
inline void U(int x,int y){
int xx=x,yy=y;if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=f[x][0];while(x^y) x=f[x][0],y=f[y][0];int z=x;
x=xx;while(x^z){if(dep[xx]-dep[x]==w[x]) ans[x]++;x=f[x][0];}if(dep[xx]-dep[x]==w[x]) ans[x]++;
y=yy;while(y^z){if(dep[xx]-dep[z]+dep[y]-dep[z]==w[y]) ans[y]++;y=f[y][0];}
}
inline void U2(int a,int b,int c,int d){
// if(f[b][0]==a) swap(a,b);f[c][0]=
}
struct FastIO{
static const int S=1048576;
char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
template<typename T>FastIO& operator >> (T&ret){
ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
}
FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
template<typename T>FastIO& operator << (T x){
if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
}
FastIO& operator << (char ch){pc(ch);return *this;}
FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
fin>>n>>m;for(register int i=1,x,y;i<n;i++) fin>>x>>y,add(x,y),add(y,x);dfs(1);tot=0;
for(register int i=1;i<=n;i++) fin>>w[i],g.push_back(w[i]+dep[i]),g.push_back(dep[i]-w[i]);bool flg=1;
for(register int i=1;i<=m;i++){
fin>>op[i]>>s[i]>>t[i];if(op[i]!=1) flg=0;if(op[i]==2) fin>>C[i]>>D[i];int x=lca(s[i],t[i]),dis=dep[s[i]]+dep[t[i]]-2*dep[x];
g.push_back(dep[s[i]]),g.push_back(dep[t[i]]-dis);
}
if(flg){
sort(g.begin(),g.end());g.erase(unique(g.begin(),g.end()),g.end());size=g.size();
for(register int i=1;i<=m;i++){
int x=lca(s[i],t[i]),dis=dep[s[i]]+dep[t[i]]-2*dep[x];
int xx=lower_bound(g.begin(),g.end(),dep[s[i]])-g.begin()+1;
int yy=lower_bound(g.begin(),g.end(),dep[t[i]]-dis)-g.begin()+1;
modify(rt[s[i]],1,size,xx,1),modify2(rt2[t[i]],1,size,yy,1);
modify(rt[x],1,size,xx,-1),modify2(rt2[x],1,size,yy,-1);
}
dfs2(1);for(register int i=1;i<=m;i++){
int x=lca(s[i],t[i]),xx=lower_bound(g.begin(),g.end(),dep[s[i]])-g.begin()+1;
int yy=lower_bound(g.begin(),g.end(),dep[x]+w[x])-g.begin()+1;if(xx==yy) ans[x]++;
}
for(register int i=1;i<=n;i++) cout<<ans[i]<<' ';return 0;
}
for(register int i=1;i<=m;i++){if(op[i]==1) U(s[i],t[i]);if(op[i]==2) U2(s[i],t[i],C[i],D[i]);if(op[i]==3) w[s[i]]=t[i];}
for(register int i=1;i<=n;i++) cout<<ans[i]<<' ';return 0;
}
正解代码如下——
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#define md double
#define LL long long
using namespace std;
const int N=3e5+100;
int gi() {
int w=0;bool q=1;char c=getchar();
while ((c<'0'||c>'9') && c!='-') c=getchar();
if (c=='-') q=0,c=getchar();
while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
return q? w:-w;
}
int head[N],next[N],to[N],n;
int Q[N],p[N],C[N],tim[N];pair<int,int>e[N],del[N];
int G[N],dep[N],fa[N],q[N],rt[N],pos[N],pre[N],L[N],R[N],dfn;
int cur[N],nxt[N],lca[N],go[N],d[N];
int Cur[N],Nxt[N],Go[N],D[N];
int s1[N],s2[N],ans[N];
int op[N],oa[N],ob[N],oc[N],od[N];
int Qu[N],Qv[N],Qs[N];
bool use[N],end[N],die[N];
inline int find(int x) { return G[x]==x?x:G[x]=find(G[x]); }
inline void dfs(int k) {
G[k]=k;L[k]=++dfn;
for (int i=cur[k];i;i=nxt[i]) if (G[go[i]]) lca[i>>1]=find(go[i]);
for (int i=head[k];i;i=next[i]) if (to[i]!=fa[k]) {
fa[to[i]]=k;
dfs(to[i]);
G[to[i]]=k;
}
R[k]=dfn;
}
inline void dfs2(int k) {
ans[k]-=s1[Q[k]+dep[k]]+s2[dep[k]-Q[k]+n];
for (int i=head[k];i;i=next[i]) if (to[i]!=fa[k]) dfs2(to[i]);
for (int i=cur[k];i;i=nxt[i]) s1[go[i]]+=d[i];
for (int i=Cur[k];i;i=Nxt[i]) s2[Go[i]]+=D[i];
ans[k]+=s1[Q[k]+dep[k]]+s2[dep[k]-Q[k]+n];
}
int main()
{
n=gi();const int B=sqrt(n);
int m=gi(),i,a,b,tot,g,l,r,k,len,t,top,fix,s,E,De;
for (i=1;i<n;i++) if ((e[i].first=gi())>(e[i].second=gi())) swap(e[i].first,e[i].second);
for (i=1;i<=n;i++) Q[i]=gi();
for (;m;m-=g) {
for (i=1;i<=n;i++) head[i]=cur[i]=fa[i]=0;
g=min(m,B);
for (i=1,De=0;i<=g;i++) if (op[i]=gi(),oa[i]=gi(),ob[i]=gi(),op[i]==2) {
oc[i]=gi(),od[i]=gi();
if (oa[i]>ob[i]) swap(oa[i],ob[i]);
if (oc[i]>od[i]) swap(oc[i],od[i]);
del[++De]=make_pair(oa[i],ob[i]);
}
sort(e+1,e+n);E=n-1;
sort(del+1,del+1+De);
for (i=1,k=1,tot=0;i<n;i++) {
while (k<=De&&del[k]<e[i]) k++;
if (del[k]==e[i]) use[i]=true;
else {
a=e[i].first,b=e[i].second;
to[++tot]=b,next[tot]=head[a],head[a]=tot;
to[++tot]=a,next[tot]=head[b],head[b]=tot;
}
}
for (t=1,len=0;t<=n;t++) if (!fa[t]) for (l=0,q[r=1]=rt[++len]=t;l!=r;) for (i=head[k=q[++l]],pos[k]=len,dep[k]=dep[fa[k]]+1;i;i=next[i]) if (to[i]!=fa[k]) fa[q[++r]=to[i]]=k;
for (i=1;i<=len;i++) cur[i]=0;
for (i=1,tot=1;i<n;i++) if (use[i]) {
a=pos[e[i].first],b=pos[e[i].second];use[i]=false;
go[++tot]=b,Go[tot]=e[i].second,nxt[tot]=cur[a],cur[a]=tot;
go[++tot]=a,Go[tot]=e[i].first,nxt[tot]=cur[b],cur[b]=tot;
}
for (t=1,top=fix=0;t<=g;t++)
if (op[t]==1) {
a=oa[t],b=ob[t];
for (l=0,pre[q[r=1]=pos[b]]=0;l!=r;) for (i=cur[k=q[++l]];i;i=nxt[i]) if (!die[i]&&i!=pre[k]) pre[q[++r]=go[i]]=i^1;
Qu[++top]=a;
for (k=pos[a];pre[k];k=go[pre[k]])
Qv[top]=Go[pre[k]^1],end[top]=false,Qu[++top]=Go[pre[k]];
Qv[top]=b,end[top]=true;
}
else if (op[t]==2) {
a=pos[oa[t]],b=pos[ob[t]];e[++E]=make_pair(oc[t],od[t]);
for (i=cur[a];i;i=nxt[i]) if (!die[i]&&go[i]==b) { die[i]=die[i^1]=true; break; }
a=pos[oc[t]],b=pos[od[t]];
go[++tot]=b,Go[tot]=od[t],nxt[tot]=cur[a],cur[a]=tot;
go[++tot]=a,Go[tot]=oc[t],nxt[tot]=cur[b],cur[b]=tot;
}
else {
a=oa[t],b=ob[t];
p[++fix]=a,C[fix]=b,tim[fix]=top;
}
while (tot>1) die[tot--]=false;
for (i=1;i<=n;i++) cur[i]=G[i]=0;
for (i=1,r=1;i<=top;i++) {
nxt[++r]=cur[Qu[i]],cur[Qu[i]]=r,go[r]=Qv[i];
nxt[++r]=cur[Qv[i]],cur[Qv[i]]=r,go[r]=Qu[i];
}
for (i=1,dfn=0;i<=len;i++) dfs(rt[i]);
for (i=0;i<=n;i++) cur[i]=Cur[i]=0;
for (i=1,l=r=s=0;i<=top;i++) {
Qs[i]=s;
nxt[++l]=cur[Qu[i]],cur[Qu[i]]=l,go[l]=dep[Qu[i]]+s,d[l]=1;
nxt[++l]=cur[fa[lca[i]]],cur[fa[lca[i]]]=l,go[l]=dep[Qu[i]]+s,d[l]=-1;
if (lca[i]!=Qv[i]) {
Nxt[++r]=Cur[Qv[i]],Cur[Qv[i]]=r,Go[r]=n+(dep[lca[i]]<<1)-dep[Qu[i]]-s,D[r]=1;
Nxt[++r]=Cur[lca[i]],Cur[lca[i]]=r,Go[r]=n+(dep[lca[i]]<<1)-dep[Qu[i]]-s,D[r]=-1;
}
end[i]?s=0:s+=dep[Qu[i]]+dep[Qv[i]]-(dep[lca[i]]<<1)+1;
}
for (i=1;i<=len;i++) dfs2(rt[i]);
for (i=cur[0];i;i=nxt[i]) s1[go[i]]+=d[i];
for (i=Cur[0];i;i=Nxt[i]) s2[Go[i]]+=D[i];
for (i=1;i<=fix;Q[a]=C[i++])
if (Q[a=p[i]]!=C[i])
for (k=top;k>tim[i];k--)
if (pos[Qu[k]]==pos[a]) {
#define in(a,b) (L[a]<=L[b]&&L[b]<=R[a])
if (in(lca[k],a)&&
((in(a,Qu[k])&&dep[Qu[k]]+Qs[k]==Q[a]+dep[a])
||(in(a,Qv[k])&&(dep[lca[k]]<<1)-dep[Qu[k]]-Qs[k]==dep[a]-Q[a]))) ans[a]--;
else if (in(lca[k],a)&&
((in(a,Qu[k])&&dep[Qu[k]]+Qs[k]==C[i]+dep[a])
||(in(a,Qv[k])&&(dep[lca[k]]<<1)-dep[Qu[k]]-Qs[k]==dep[a]-C[i]))) ans[a]++;
}
sort(e+1,e+1+E);
for (i=1,k=1,top=0;i<=E;i++) {
while (k<=De&&del[k]<e[i]) k++;
if (k<=De&&del[k]==e[i]) k++;
else e[++top]=e[i];
}
}
for (i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}