---

 首先肯定考虑树剖，这里没有要求区间加，所以可以用树状数组维护，不会卡常的

这里是边权，可以转化为点权：让每条边连接的较深的节点的点权等于边权即可，然后计算的时候减去lca

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #define MAXN 300005  6 #define LOG 20  7 using namespace std;  8 int read(){  9     int x=0;char ch=getchar(); 10     while(ch<'0'||ch>'9'){ch=getchar();} 11     while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();} 12     return x; 13 } 14 int n,T; 15 int a[MAXN],dat[MAXN]; 16 int dep[MAXN],size[MAXN],gs[MAXN],fa[20][MAXN]; 17 int top[MAXN],tree[MAXN],pre[MAXN],tot; 18 int first[MAXN],nxt[MAXN<<1],to[MAXN<<1],cnt; 19 int id[MAXN],tmp; 20  21 void add(int x,int y){ 22     nxt[++cnt]=first[x];first[x]=cnt;to[cnt]=y; 23     nxt[++cnt]=first[y];first[y]=cnt;to[cnt]=x; 24 } 25 int lca(int x,int y){ 26     if(dep[x]
          
           >=1,p++){ 30         if(k&1){ 31             x=fa[p][x]; 32         } 33     } 34     if(x==y){ 35         return x; 36     } 37     for(int k=LOG-1;k>=0;k--){ 38         if(fa[k][x]!=fa[k][y]){ 39             x=fa[k][x],y=fa[k][y]; 40         } 41     } 42     return fa[0][x]; 43 } 44 void change(int k,int x){ 45     while(k<=n){ 46         dat[k]+=x; 47         k+=(k&-k); 48     } 49 } 50 int query(int k){ 51     int ret=0; 52     while(k>=1){ 53         ret+=dat[k]; 54         k-=(k&-k); 55     } 56     return ret; 57 } 58 void dfs1(int x){ 59     size[x]=1; 60     for(int e=first[x];e;e=nxt[e]){ 61         int y=to[e]; 62         if(y==fa[0][x]){ 63             continue; 64         } 65         fa[0][y]=x; 66         dep[y]=dep[x]+1; 67         dfs1(y); 68         size[x]+=size[y]; 69         if(size[y]>size[gs[x]]){ 70             gs[x]=y; 71         } 72     } 73 } 74 void dfs2(int x,int t){ 75     top[x]=t; 76     tree[x]=(++tot); 77     pre[tot]=x; 78     if(!gs[x]){ 79         return; 80     } 81     dfs2(gs[x],t); 82     for(int e=first[x];e;e=nxt[e]){ 83         int y=to[e]; 84         if(y==fa[0][x]||y==gs[x]){ 85             continue; 86         } 87         dfs2(y,y); 88     } 89 } 90 int ask(int x,int y){ 91     int f1=top[x],f2=top[y]; 92     if(dep[f1]
          
         
        
       
      

也可以是树上差分，用树状数组+dfs序，本质上是差不多的

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #define MAXN 300005  6 #define LOG 20  7 using namespace std;  8 int read(){  9     int x=0;char ch=getchar(); 10     while(ch<'0'||ch>'9'){ch=getchar();} 11     while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();} 12     return x; 13 } 14 int n,T; 15 int first[MAXN],nxt[MAXN<<1],to[MAXN<<1],cnt; 16 int pin[MAXN],pout[MAXN],tot; 17 int dat[MAXN<<1]; 18 int fa[LOG][MAXN],dep[MAXN]; 19 int id[MAXN],tmp; 20 void change(int k,int x){ 21     while(k<=(n<<1)){ 22         dat[k]+=x; 23         k+=(k&-k); 24     } 25 } 26 int query(int k){ 27     int ret=0; 28     while(k>=1){ 29         ret+=dat[k]; 30         k-=(k&-k); 31     } 32     return ret; 33 } 34 void add(int x,int y){ 35     nxt[++cnt]=first[x];first[x]=cnt;to[cnt]=y; 36     nxt[++cnt]=first[y];first[y]=cnt;to[cnt]=x; 37 } 38 int lca(int x,int y){ 39     if(dep[x]
          
           >=1,p++){ 43         if(k&1){ 44             x=fa[p][x]; 45         } 46     } 47     if(x==y){ 48         return x; 49     } 50     for(int k=LOG-1;k>=0;k--){ 51         if(fa[k][x]!=fa[k][y]){ 52             x=fa[k][x],y=fa[k][y]; 53         } 54     } 55     return fa[0][x]; 56 } 57 void dfs(int x){ 58     pin[x]=(++tot); 59     for(int e=first[x];e;e=nxt[e]){ 60         int y=to[e]; 61         if(y==fa[0][x]){ 62             continue; 63         } 64         dep[y]=dep[x]+1; 65         fa[0][y]=x; 66         dfs(y); 67     } 68     pout[x]=(++tot); 69 } 70 int ask(int x,int y){ 71     int t=query(pin[x])+query(pin[y])-2*query(pin[lca(x,y)]); 72     return (t<=0); 73 } 74 void init(){ 75     n=read(); T=read(); 76     for(int i=1;i