反思
A
感觉有点降智，一眼 m a n a c h e r manacher manacher，但很久才想到可以二分，然后就转化成了一个区间最大值问题
B
感觉有点弱智的题，题目不难，一开始算复杂度的时候认为 [ 1.5 − 3 ] ∗ 1 0 8 [1.5-3]*10^8 [1.5−3]∗108 冲不过 1 s 1s 1s，事实上开了 O 2 O2 O2 只要 800 m s 800ms 800ms
C
乱搞大爱！！！
但忘记
l
o
n
g
l
o
n
g
×
l
o
n
g
l
o
n
g
long\;long \times long\; long
longlong×longlong 会爆！！！
题解
比赛链接
A
感觉
m
a
n
a
c
h
e
r
manacher
manacher 挺显然的，因为是回文
然后的询问二分想了很久才想到，深感自己菜的本质，写代码时一些细节也调了很久
B
没什么好说的，直接 d p dp dp，压一下状态开冲！感觉人傻常数大，可能不加那个小剪枝就被卡常了
C
我是乱搞人！！！直接
100
p
t
s
100pts
100pts，我惊了！
正解是维护凸包，但我不会，先不补了
D
感觉是一道挺像暴力的数据结构
注意到
k
k
k 很小，所以可以估计到
k
k
k 只是用来卡常用的
所以我们考虑一组询问可以在
O
(
n
l
o
g
n
)
−
O
(
n
l
o
g
2
n
)
O(nlogn)-O(nlog^2n)
O(nlogn)−O(nlog2n) 的时间复杂度内求解
考虑
m
e
x
mex
mex 具有可二分性，所以先二分
对于
m
i
d
>
1
mid>1
mid>1 的情况，考虑找到一条最短的路径覆盖
0
0
0 到
m
i
d
−
1
mid-1
mid−1 中所有的点，如果不能，就不行，然后我们考虑从两个端点往两边拓展，然后塞到
t
r
i
e
trie
trie 树上查询有没有异或和在
l
−
r
l-r
l−r 之间的数，这个是容易实现的
对于
m
i
d
=
1
mid=1
mid=1 的情况，我们即要找到一条路径的端点在以
0
0
0 为根的两棵子树中，这个也是可以用
t
r
i
e
trie
trie 树维护的
时间复杂度
O
(
k
n
l
o
g
2
n
)
O(knlog^2n)
O(knlog2n)（听说
l
o
g
2
log^2
log2 被卡了，不过没事，
n
f
l
s
nfls
nfls 不会重测代码 ）
#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int n,q,l,r,dis[N];
int depth[N],up[N][20];
int e[N<<1],w[N<<1],ne[N<<1],h[N],idx;
int st[N],ed[N],lim;
int ox[N],cnt;
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
int get_lca(int x,int y){
if(depth[x]>depth[y]) swap(x,y);
for(int i=18;i>=0;i--) if(depth[up[y][i]]>=depth[x]) y=up[y][i];
if(x==y) return x;
for(int i=18;i>=0;i--) if(up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i];
return up[x][0];
}
int get_dist(int x,int y){ return depth[x]+depth[y]-2*depth[get_lca(x,y)];}
void insert(int u,int fa,int xo){
ox[++cnt]=xo;
for(int i=h[u];~i;i=ne[i]) if(e[i]!=fa) insert(e[i],u,xo^w[i]);
}
struct Trie{
int idx,tr[N*31][2],cnt[N*31];
void clear(){
for(int i=0;i<=idx;i++) tr[i][0]=tr[i][1]=cnt[i]=0;
idx=0;
}
void insert(int v){
int p=0;
for(int i=30;i>=0;i--){
int c=v>>i&1;
if(!tr[p][c]) tr[p][c]=++idx;
p=tr[p][c],cnt[p]++;
}
}
int query(int v,int lim){
if(lim<0) return 0;
int p=0,res=0;
for(int i=30;i>=0;i--){
int c1=lim>>i&1,c2=v>>i&1;
if(c1){
res+=cnt[tr[p][c2]];
if(!tr[p][c2^1]) return res;
p=tr[p][c2^1];
}
else{
if(!tr[p][c2]) return res;
p=tr[p][c2];
}
}
return res+cnt[p];
}
}trie;
bool check1(int mid){//mid>1的情况
if(mid>lim) return false;
int S=st[mid],E=ed[mid];
int d=get_dist(S,E),fas,fae;
for(int i=h[S];~i;i=ne[i]) if(get_dist(e[i],E)==d-1) fas=e[i];
for(int i=h[E];~i;i=ne[i]) if(get_dist(e[i],S)==d-1) fae=e[i];
cnt=0,insert(S,fas,0);
trie.clear();
for(int i=1;i<=cnt;i++) trie.insert(ox[i]);
cnt=0,insert(E,fae,dis[S]^dis[E]);
for(int i=1;i<=cnt;i++) if(trie.query(ox[i],r)-trie.query(ox[i],l-1)) return true;
return false;
}
bool check2(){
trie.clear();
for(int i=h[0];~i;i=ne[i]){
cnt=0,insert(e[i],0,w[i]);
for(int j=1;j<=cnt;j++) if(trie.query(ox[j],r)-trie.query(ox[j],l-1)) return true;
for(int j=1;j<=cnt;j++) trie.insert(ox[j]);
}
return false;
}
bool insert_node(int x){
int d1=get_dist(x,st[x-1]),d2=get_dist(x,ed[x-1]),d3=get_dist(st[x-1],ed[x-1]);
if(d1+d2==d3) return true;
if(d1+d3==d2){ st[x]=x;return true;}
if(d2+d3==d1){ ed[x]=x;return true;}
return false;
}
void dfs(int u,int fa){
depth[u]=depth[fa]+1;
for(int i=h[u];~i;i=ne[i]) if(e[i]!=fa) dis[e[i]]=dis[u]^w[i],up[e[i]][0]=u,dfs(e[i],u);
}
void add(int x,int y,int z){ e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;}
int main(){
freopen("nim.in","r",stdin);
freopen("nim.out","w",stdout);
n=read(),q=read();
memset(h,-1,sizeof(h));
for(int i=1;i<n;i++){
int x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
dfs(0,0);
for(int j=1;j<=18;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];
st[0]=ed[0]=0,st[1]=0,ed[1]=1;
for(int i=2;i<=n;i++){
st[i]=st[i-1],ed[i]=ed[i-1];
if(!insert_node(i)) break;
lim=i;
}
while(q--){
l=read(),r=read();
int lb=1,rb=n+1;
while(lb<rb-1){
int mid=(lb+rb)>>1;
check1(mid-1)?lb=mid:rb=mid;
}
if(lb==1){
if(check2()) puts("1");
else puts("0");
}
else printf("%d\n",lb);
}
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}
