没看过正解。。应该是些乱七八糟想不出来的东西

解法1：

首先，必须要做的是将每条路径拆成2个直的路径

那么对于那条从深度大的到深度小的路径 dep[x]-dep[y]应该等于观察时间

那么就可以在这些点打标记

那问题在于怎么找这些点

可以把深度为x的数组用vector搞出来

然后每次判断一下x里面的元素是否在他的子树中（判断一下lca就好了）

树剖判断一下每个点的覆盖次数

对于另一条路径同理做

代码：

解法2：

这个解法复杂度是可以分析出来的

首先还是把路径拆成两条

那么对于那条从深度大的到深度小的路径

考虑启发式合并

对于每个点维护一颗splay表示子树中出现的dep值的个数

将路径顶端和底端分别在该点打标记

访问到顶端时删除底端时插入

由于每一次向上会导致所有元素的权值变化所以可以加一个标记（插入时减掉这个值）

那么到查询点的时候就在splay上查询就可以了

那么复杂度是nlogn*splay的复杂度 也就是nlog^2n  不过splay的常数感觉这方法还是很虚啊。。。

还有就是splay的insert操作之后要splay一下

防止是这颗树的第一个节点

代码：

#include 
     
      using namespace std;#define maxn 6200000#define maxn2 310000int count2[maxn],leftson[maxn],rightson[maxn],fa[maxn],root[maxn2];struct re{  int a,b,c;}a[maxn2*2];int ans[maxn2],bz[maxn2][20],dep[maxn2],vw[maxn2],head[maxn2],l,last[maxn2];int hf[maxn2],cc[maxn2],dd[maxn2],lcaa[maxn2],num[maxn],num2,data[maxn];int n,m;vector
      
        ve[maxn];inline void updata(int x){  count2[x]=count2[leftson[x]]+count2[rightson[x]]+1;}inline void rotate(int x,int y){  int father=fa[x];  if (y==1)  {    rightson[father]=leftson[x];    if (leftson[x]) fa[leftson[x]]=father;  } else  {    leftson[father]=rightson[x];    if (rightson[x]) fa[rightson[x]]=father;  }  fa[x]=fa[father];  if (fa[father])  {    if (leftson[fa[father]]==father) leftson[fa[father]]=x;    else rightson[fa[father]]=x;  }  fa[father]=x;  if (y==1) leftson[x]=father; else rightson[x]=father;  updata(father); updata(x);}inline void splay(int k,int x,int goal){  if (x==root[k]) return;  int father=fa[x];  while (father!=goal)  {    if (fa[father]==goal)    {      if (x==leftson[father]) rotate(x,2); else rotate(x,1);    } else    {      if (father==leftson[fa[father]])      {        if (x==leftson[father]) rotate(father,2),rotate(x,2);        else rotate(x,1),rotate(x,2);      } else      {        if (x==rightson[father]) rotate(father,1),rotate(x,1);        else rotate(x,2),rotate(x,1);      }    }    father=fa[x];  }  if (goal==0) root[k]=x;}inline void dfs(int x,int y){  bz[x][0]=y; dep[x]=dep[y]+1;   int u=head[x];  while (u)  {    int v=a[u].b;    if (v!=y) dfs(v,x);    u=a[u].a;  }}inline int get_lca(int x,int y){   if (dep[x]
       
        =0;i--)     if (dep[bz[x][i]]>=dep[y]) x=bz[x][i];   if (x==y) return(x);   for (int i=19;i>=0;i--)     if (bz[x][i]!=bz[y][i])     {       x=bz[x][i],y=bz[y][i];     }   return(bz[x][0]);}inline void arr(int x,int y){  a[++l].a=head[x];  a[l].b=y;  head[x]=l;}inline void insert(int x,int v,int w){  int tmp=x;x=root[x];  while (x)  {    if (data[x]==v) break;    count2[x]++;    if (v
        
         data[x]) rightson[x]=num2;      else leftson[x]=num2;    }    splay(tmp,num2,0);  }}inline void delete1(int k){  int x=leftson[root[k]];  if (x==0)  {    root[k]=rightson[root[k]]; fa[root[k]]=0; return;  }  while (rightson[x]) x=rightson[x];  splay(k,x,root[k]);  rightson[x]=rightson[root[k]];  if (rightson[root[k]]) fa[rightson[root[k]]]=x;  updata(x);  fa[x]=0; root[k]=x;}inline int search(int x,int goal){  x=root[x];  while (1)  {    if (data[x]==goal) return(x);    if (data[x]
         
          1) num[tmp]--;      else       {        splay(x,tmp,0);         delete1(x);      }  }}int main(){  freopen("noip.in","r",stdin);  freopen("noip.out","w",stdout);  std::ios::sync_with_stdio(false);  cin>>n>>m;  int c,d;  for (int i=1;i<=n-1;i++)    cin>>c>>d,arr(c,d),arr(d,c);  for (int i=1;i<=n;i++)    cin>>vw[i];  dfs(1,0);  for (int i=1;i<=19;i++)    for (int j=1;j<=n;j++)      bz[j][i]=bz[bz[j][i-1]][i-1];  for (int i=1;i<=m;i++)  {    cin>>c>>d;    cc[i]=c; dd[i]=d;    int w=get_lca(c,d);    lcaa[i]=w;    hf[i]=dep[c]-dep[w];  }  for (int i=1;i<=m;i++)  {    ve[cc[i]].push_back(0); ve[cc[i]].push_back(0);    ve[lcaa[i]].push_back(hf[i]); ve[lcaa[i]].push_back(1);  }  dfs2(1,0,1);  memset(leftson,0,sizeof(leftson));  memset(rightson,0,sizeof(rightson));  memset(num,0,sizeof(num));  memset(count2,0,sizeof(count2));  memset(fa,0,sizeof(fa));  memset(root,0,sizeof(root));  memset(last,0,sizeof(last)); num2=0;  memset(data,0,sizeof(data));  for (int i=1;i<=n;i++)  {    vector
          
            tmp; swap(tmp,ve[i]); // ve[i].clear(); } for (int i=1;i<=m;i++) { ve[dd[i]].push_back(hf[i]+dep[dd[i]]-dep[lcaa[i]]); ve[dd[i]].push_back(0); ve[lcaa[i]].push_back(hf[i]); ve[lcaa[i]].push_back(1); } dfs2(1,0,-1); for (int i=1;i<=m;i++) { if (hf[i]==vw[lcaa[i]]) ans[lcaa[i]]--; } for (int i=1;i<=n-1;i++) cout<
           
            <<" "; cout<