题意:
一棵树,多次询问,每次询问k条路径上的相交点个数,k只有几十个
题解:
显然,对于每个路径进行树链+1,答案就是为k的点的个数,由于询问的特殊性,我们直接用odt维护就行
最后速度还好
#include <bits/stdc++.h> #define endl '\n' #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define rep(ii,a,b) for(int ii=a;ii<=b;++ii) #define forn(ii,now) for(int ii=head[now];ii;ii=e[ii].next) using namespace std; const int maxn=1e6+10,maxm=2e6+10; int casn,n,m,k; class odtree{public: struct segnode{ int l,r;mutable int val; bool operator<(const segnode &b)const {return l<b.l;} }; set<segnode> nd; void init(int n=maxn-5){nd.clear();nd.insert({1,n,0});} auto split(int pos){ auto it=nd.lower_bound({pos,pos,0}); if(it!=nd.end()&&it->l==pos) return it; it--; int l=it->l,r=it->r,val=it->val; nd.erase(it);nd.insert({l,pos-1,val}); return nd.insert({pos,r,val}).fi; } void update(int l,int r,int val){ auto itr=split(r+1),itl=split(l); for(auto it=itl;it!=nd.end()&&(it->l)<=r;++it){ ++(it->val); } } int query(int l,int r,int k){ auto itr=split(r+1),itl=split(l); int sum=0; for(auto it=itl;it!=nd.end()&&(it->l)<=r;++it){ if((it->val)==k) sum+=(it->r)-(it->l)+1; } return sum; } }tree; class chain{public: struct node{int to,next;}e[maxn<<1]; int head[maxn],nume,mp[maxn]; inline void add(int a,int b){ e[++nume]={b,head[a]}; head[a]=nume; } int ltop[maxn],fa[maxn],deep[maxn]; int sz[maxn],remp[maxn]; int son[maxn],cnt; void init(int n){rep(i,1,n) head[i]=0;cnt=0,nume=1;} void dfs1(int now=1,int pre=1,int d=0){ deep[now]=d,fa[now]=pre,sz[now]=1,son[now]=0; forn(i,now){ int to=e[i].to; if(to!=pre) { dfs1(to,now,d+1); sz[now]+=sz[to]; if(sz[to]>sz[son[now]]) son[now]=to; } } } void dfs2(int now=1,int pre=1,int sp=1){ ltop[now]=sp;mp[now]=++cnt;remp[cnt]=now; if(son[now]) dfs2(son[now],now,sp); forn(i,now){ int to=e[i].to; if(to!=son[now]&&to!=pre) dfs2(to,now,to); } } void update(int a,int b,int val){ while(ltop[a]!=ltop[b]){ if(deep[ltop[a]]<deep[ltop[b]])swap(a,b); tree.update(mp[ltop[a]],mp[a],val); a=fa[ltop[a]]; } if(deep[a]>deep[b])swap(a,b); tree.update(mp[a],mp[b],val); } int query(int a,int b,int k){ int sum=0; while(ltop[a]!=ltop[b]){ if(deep[ltop[a]]<deep[ltop[b]])swap(a,b); sum+=tree.query(mp[ltop[a]],mp[a],k); a=fa[ltop[a]]; } if(deep[a]>deep[b])swap(a,b); sum+=tree.query(mp[a],mp[b],k); return sum; } int lca(int x,int y){ for(;ltop[x]!=ltop[y];deep[ltop[x]]>deep[ltop[y]]?x=fa[ltop[x]]:y=fa[ltop[y]]); return deep[x]<deep[y]?x:y; } void div(){dfs1();dfs2();} }g; int main(){ IO; cin>>casn; rep($,1,casn){ cout<<"Case "<<$<<":"<<endl; cin>>n;g.init(n); rep(i,2,n){ int a,b;cin>>a>>b; g.add(a,b);g.add(b,a); } g.div();cin>>m; while(m--){ cin>>k; int a,b; tree.init(n); rep(_,1,k){ cin>>a>>b; g.update(a,b,1); } cout<<g.query(a,b,k)<<endl; } } }