题意:有一棵树,每个点有一个权值要求找最小的一对点,路径上的乘积mod1e6+3为k

题解:点分治,挨个把子树更新,每次把子树和现有的map里找满足条件的点对,然后更新子树到map里,map维护的是每个到根的乘积值最小的点.

//#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")//#pragma GCC optimize("unroll-loops")#include
    
     #define fi first#define se second#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define vi vector
     
      #define mod 1000003#define C 0.5772156649#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define pil pair
      
       #define pli pair
       
        #define pii pair
        
         #define cd complex
         
          #define ull unsigned long long#define base 1000000000000000000#define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double eps=1e-6;const int N=100000+10,maxn=1000000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;struct edge{ int to,Next;}e[N*2];int cnt,head[N];void add(int u,int v){ e[cnt].to=v; e[cnt].Next=head[u]; head[u]=cnt++;}int n,k,inv[maxn];bool vis[N];int sz[N],zx[N],a[N];map
          
           ma;int x,y;vector
           
            
              >te;void init(){ inv[1]=1; for(int i=2;i
             
              yy)swap(xx,yy); if(xx
              
               yy)swap(xx,yy); if(xx