题目来源：2025 Wuhan University of Technology Programming Contest
比赛链接：Dashboard - 2025 Wuhan University of Technology Programming Contest - Codeforces
题目大意：
Solution：
首先肯定要预处理出以每个节点为起点出发获得的分数。然后就可以把树上的问题变成普通序列区间上的问题处理了。
很显然：
MAX 的答案就是区间长度
MIN 的答案就是区间众数的出现次数（若有多个众数，只算单个众数的出现次数）
于是答案就分为两个部分，一个树上预处理，一个维护区间众数出现次数。
第一部分可以树上启发式合并，用一个 set 维护当前子树内的连续区间，一个 multiset 维护当前所有连续区间的长度。当我们每加入一个新的点时，合并左右临接的区间，于是我们维护的区间一定是不相交的。
至于第二部分，直接离线询问莫队处理即可。
（第一次打的时候不知道如何用 set 维护区间，用数组存区间端点，又加了一个 goodr 表示当前维护的所有右端点，过程相对复杂，容易错，但好在没怎么调试，把两种写法代码都放在下面。）
Code1：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
#define N 100005
int n,m,cnt,B,res;
int a[N],st[N],bel[N],dfn[N],siz[N],son[N],id[N],w[N],num[N],ld[N],rd[N],col[N],tot[N]; // num是数字i出现的次数
struct Edge
{
int next,to;
}ed[N << 1];
struct Query
{
int l,r,id;
}q[N],ans[N];
multiset<int> s,goodr; // goodr存的是有效右端点
int max(int x,int y) { return x > y ? x : y ; }
int cmp(Query x,Query y)
{
if(bel[x.l] == bel[y.l]) return x.r < y.r ;
return bel[x.l] < bel[y.l] ;
}
void added(int u,int v)
{
ed[++ cnt].next = st[u];
ed[cnt].to = v;
st[u] = cnt;
return;
}
void pdfs(int x,int fa)
{
siz[x] = 1;
dfn[x] = ++ cnt;
id[cnt] = x;
for (int i = st[x]; ~i ;i = ed[i].next)
{
int rec = ed[i].to;
if(rec == fa) continue;
pdfs(rec,x);
siz[x] += siz[rec];
if(!son[x] || siz[rec] > siz[son[x]]) son[x] = rec;
}
return;
}
void calc(int x)
{
x = a[x];
if(!num[x])
{
if(ld[x - 1] && rd[x + 1])
{
int lenl,lenr;
lenl = x - ld[x - 1];
lenr = rd[x + 1] - x;
auto it = s.lower_bound(lenl);
s.erase(it);
it = s.lower_bound(lenr);
s.erase(it);
s.insert(lenl + lenr + 1);
int tl,tr;
tl = ld[x - 1];
tr = rd[x + 1];
ld[rd[x + 1]] = tl,rd[ld[x - 1]] = tr;
ld[x - 1] = rd[x + 1] = 0;
it = goodr.lower_bound(x - 1);
goodr.erase(x - 1);
}
else if(ld[x - 1])
{
int len = x - ld[x - 1];
auto it = s.lower_bound(len);
s.erase(it);
s.insert(len + 1);
ld[x] = ld[x - 1];
ld[x - 1] = 0;
rd[ld[x]] = x;
it = goodr.lower_bound(x - 1);
goodr.erase(x - 1);
goodr.insert(x);
}
else if(rd[x + 1])
{
int len = rd[x + 1] - x;
auto it = s.lower_bound(len);
s.erase(it);
s.insert(len + 1);
rd[x] = rd[x + 1];
rd[x + 1] = 0;
ld[rd[x]] = x;
}
else
{
ld[x] = rd[x] = x;
s.insert(1);
goodr.insert(x);
}
}
++ num[x];
return;
}
void del(int x)
{
x = a[x];
-- num[x];
if(!num[x])
{
auto it = goodr.lower_bound(x);
int tr = *it;
int tl = ld[tr];
int len = tr - tl + 1;
it = s.lower_bound(len);
s.erase(it);
if(tl < x)
{
int lenl = x - tl;
s.insert(lenl);
rd[tl] = x - 1;
ld[x - 1] = tl;
goodr.insert(x - 1);
}
else rd[tl] = 0;
if(tr > x)
{
int lenr = tr - x;
s.insert(lenr);
ld[tr] = x + 1;
rd[x + 1] = tr;
}
else
{
ld[tr] = 0;
it = goodr.lower_bound(x);
goodr.erase(it);
}
}
return;
}
void dfs(int x,int fa,int op)
{
for (int i = st[x]; ~i ;i = ed[i].next)
{
int rec = ed[i].to;
if(rec == fa || rec == son[x]) continue;
dfs(rec,x,0);
}
if(son[x]) dfs(son[x],x,1);
calc(x);
for (int i = st[x]; ~i ;i = ed[i].next)
{
int rec = ed[i].to;
if(rec == fa || rec == son[x]) continue;
for (int j = dfn[rec];j <= dfn[rec] + siz[rec] - 1;++ j)
calc(id[j]);
}
auto it = s.rbegin();
w[x] = *it;
if(!op)
{
for (int i = dfn[x];i <= dfn[x] + siz[x] - 1;++ i)
del(id[i]);
}
return;
}
void add(int x)
{
x = w[x];
-- tot[col[x]];
++ col[x];
++ tot[col[x]];
res = max(res,col[x]);
return;
}
void sub(int x)
{
x = w[x];
-- tot[col[x]];
if(!tot[col[x]] && res == col[x]) -- res;
-- col[x];
++ tot[col[x]];
return;
}
int main()
{
memset(st,-1,sizeof st);
scanf("%d%d",&n,&m),cnt = res = 0,B = (int)sqrt(n);
for (int i = 1;i <= n;++ i) scanf("%d",&a[i]),bel[i] = (i - 1) / B + 1;
for (int i = 1,u,v;i < n;++ i)
scanf("%d%d",&u,&v),added(u,v),added(v,u);
cnt = 0;
pdfs(1,0);
dfs(1,0,1);
for (int i = 1;i <= m;++ i)
scanf("%d%d",&q[i].l,&q[i].r),q[i].id = i;
sort(q + 1,q + m + 1,cmp);
int l,r;
l = 1,r = 0;
for (int i = 1;i <= m;++ i)
{
while (l > q[i].l) add(-- l);
while (l < q[i].l) sub(l ++);
while (r < q[i].r) add(++ r);
while (r > q[i].r) sub(r --);
ans[q[i].id].l = res;
ans[q[i].id].r = r - l + 1;
}
for (int i = 1;i <= m;++ i) printf("%d %d\n",ans[i].l,ans[i].r);
return 0;
}Code2：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
#define N 100005
int n,m,cnt,B,res;
int a[N],st[N],bel[N],dfn[N],siz[N],son[N],id[N],w[N],num[N],ld[N],rd[N],col[N],tot[N];
struct Edge
{
int next,to;
}ed[N << 1];
struct Query
{
int l,r,id;
}q[N],ans[N];
multiset<int> len;
set<pair <int,int> > s;
int max(int x,int y) { return x > y ? x : y ; }
int cmp(Query x,Query y)
{
if(bel[x.l] == bel[y.l]) return x.r < y.r ;
return bel[x.l] < bel[y.l] ;
}
void added(int u,int v)
{
ed[++ cnt].next = st[u];
ed[cnt].to = v;
st[u] = cnt;
return;
}
void pdfs(int x,int fa)
{
siz[x] = 1;
dfn[x] = ++ cnt;
id[cnt] = x;
for (int i = st[x]; ~i ;i = ed[i].next)
{
int rec = ed[i].to;
if(rec == fa) continue;
pdfs(rec,x);
siz[x] += siz[rec];
if(!son[x] || siz[rec] > siz[son[x]]) son[x] = rec;
}
return;
}
void calc(int x)
{
x = a[x];
int lenl,lenr;
if(!num[x])
{
auto it = s.upper_bound({x,N});
int flag = 0;
if(it != s.end() && it != s.begin())
{
auto rseg = *it;
-- it;
auto lseg = *it;
++ it;
lenl = lseg.second - lseg.first + 1;
lenr = rseg.second - rseg.first + 1;
if(lseg.second == x - 1 && rseg.first == x + 1)
{
auto itlen = len.lower_bound(lenl);
len.erase(itlen);
itlen = len.lower_bound(lenr);
len.erase(itlen);
len.insert(lenl + lenr + 1);
s.erase({lseg.first,lseg.second});
s.erase({rseg.first,rseg.second});
s.insert({lseg.first,rseg.second});
flag = 1;
}
}
if(!flag)
{
if(it != s.end())
{
auto rseg = *it;
lenr = rseg.second - rseg.first + 1;
if(rseg.first == x + 1)
{
auto itlen = len.lower_bound(lenr);
len.erase(itlen);
len.insert(lenr + 1);
s.erase({rseg.first,rseg.second});
s.insert({x,rseg.second});
flag = 1;
}
}
if(!flag)
{
if(it != s.begin())
{
-- it;
auto lseg = *it;
++ it;
lenl = lseg.second - lseg.first + 1;
if(lseg.second == x - 1)
{
auto itlen = len.lower_bound(lenl);
len.erase(itlen);
len.insert(lenl + 1);
s.erase({lseg.first,lseg.second});
s.insert({lseg.first,x});
flag = 1;
}
}
}
if(!flag)
{
s.insert({x,x});
len.insert(1);
}
}
}
++ num[x];
return;
}
void del(int x)
{
x = a[x];
-- num[x];
if(!num[x])
{
auto it = s.upper_bound({x,N});
-- it;
auto seg = *it;
int lenl = x - seg.first;
int lenr = seg.second - x;
s.erase({seg.first,seg.second});
if(seg.first < x && seg.second > x)
{
auto itlen = len.lower_bound(lenl + lenr + 1);
len.erase(itlen);
len.insert(lenl);
len.insert(lenr);
s.insert({seg.first,x - 1});
s.insert({x + 1,seg.second});
}
else if(seg.first < x)
{
auto itlen = len.lower_bound(lenl + 1);
len.erase(itlen);
len.insert(lenl);
s.insert({seg.first,x - 1});
}
else if(seg.second > x)
{
auto itlen = len.lower_bound(lenr + 1);
len.erase(itlen);
len.insert(lenr);
s.insert({x + 1,seg.second});
}
else
{
auto itlen = len.lower_bound(1);
len.erase(itlen);
}
}
return;
}
void dfs(int x,int fa,int op)
{
for (int i = st[x]; ~i ;i = ed[i].next)
{
int rec = ed[i].to;
if(rec == fa || rec == son[x]) continue;
dfs(rec,x,0);
}
if(son[x]) dfs(son[x],x,1);
calc(x);
for (int i = st[x]; ~i ;i = ed[i].next)
{
int rec = ed[i].to;
if(rec == fa || rec == son[x]) continue;
for (int j = dfn[rec];j <= dfn[rec] + siz[rec] - 1;++ j)
calc(id[j]);
}
auto it = len.rbegin();
w[x] = *it;
if(!op)
{
for (int i = dfn[x];i <= dfn[x] + siz[x] - 1;++ i)
del(id[i]);
}
return;
}
void add(int x)
{
x = w[x];
-- tot[col[x]];
++ col[x];
++ tot[col[x]];
res = max(res,col[x]);
return;
}
void sub(int x)
{
x = w[x];
-- tot[col[x]];
if(!tot[col[x]] && res == col[x]) -- res;
-- col[x];
++ tot[col[x]];
return;
}
int main()
{
memset(st,-1,sizeof st);
scanf("%d%d",&n,&m),cnt = res = 0,B = (int)sqrt(n);
for (int i = 1;i <= n;++ i) scanf("%d",&a[i]),bel[i] = (i - 1) / B + 1;
for (int i = 1,u,v;i < n;++ i)
scanf("%d%d",&u,&v),added(u,v),added(v,u);
cnt = 0;
pdfs(1,0);
dfs(1,0,1);
for (int i = 1;i <= m;++ i)
scanf("%d%d",&q[i].l,&q[i].r),q[i].id = i;
sort(q + 1,q + m + 1,cmp);
int l,r;
l = 1,r = 0;
for (int i = 1;i <= m;++ i)
{
while (l > q[i].l) add(-- l);
while (l < q[i].l) sub(l ++);
while (r < q[i].r) add(++ r);
while (r > q[i].r) sub(r --);
ans[q[i].id].l = res;
ans[q[i].id].r = r - l + 1;
}
for (int i = 1;i <= m;++ i) printf("%d %d\n",ans[i].l,ans[i].r);
return 0;
}