参考博客：

https://www.cnblogs.com/ice-wing/p/7709311.html

https://www.luogu.org/blog/sincereactor/shu-shang-ci-fen-di-liang-zhong-sai-lu

https://blog.csdn.net/Fine_rose/article/details/77991839

https://blog.csdn.net/ArliaStark/article/details/80720181

已知路径求被所有路径覆盖的边

首先对已知的这 n 条路径的起点a和终点b的权值+1，并对lca(a,b)的权值-2 。

从根节点开始深搜，回溯时将其本身的权值加上所有子节点的权值。

那么满足要求的边就是权值等于n的节点与其父节点所连的边。

例题：

P2680

询问m条链中，删去一条边，使权值最大的链权值最小。

思路：

二分最大链的权值L。

对于链长小于等于L的，不用管。

对于链长大于L的，要确保删的这条边在该链上。

所以选定的这条边要被所有链长大于L的链所覆盖，在符合条件的边里选最长的那一条才最优，然后判断当前最长链-该边的权值是否小于这个二分的最大链的权值即可。

代码：

struct edge
{
    int to;
    int cost;
    int next;
}eg[300010*2];
struct imfo
{
    int a,b,lc;
    int len;
}p[300010];
int val[300010];//i->par[i]的权值
int top;
int head[300010];
int tot[300010];
int son[300010];
int idx[300010];
int topp[300010];
int par[300010];
int dep[300010];
int dis[300010];
int n,m;
int mark[300010];
int pre[300010];
int maxlen;
int cnt;
inline int read()
{
    char c=getchar();
    int x=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x;
}
void add(int a,int b,int t)
{
    eg[top].to=b;
    eg[top].cost=t;
    eg[top].next=head[a];
    head[a]=top++;
}
int dfs1(int id,int fa,int depth,int sum)
{
    dep[id]=depth;
    tot[id]=1;
    dis[id]=sum;
    par[id]=fa;
    int maxson=-1;
    son[id]=0;
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(temp==fa)continue;
        val[eg[i].to]=eg[i].cost;
        tot[id]+=dfs1(eg[i].to,id,depth+1,sum+val[eg[i].to]);
        if(tot[temp]>maxson)
        {
            son[id]=temp;
            maxson=tot[temp];
        }
    }
    return tot[id];
}
void dfs2(int id,int topf)
{
    idx[id]=++cnt;
    topp[id]=topf;
    if(son[id]==0)return;     //子节点的son为0
    dfs2(son[id],topf);     //优先标记重儿子
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(idx[temp]==0)
            dfs2(temp,temp);     //每一条链以轻儿子为起点
    }
}
int lca(int x,int y)
{
    while(topp[x]!=topp[y])
    {
        if(dep[topp[x]]<dep[topp[y]])swap(x,y);     //谁的top低谁就往上走
        x=par[topp[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
int calcpre(int id,int fa)
{
    pre[id]=0;
    for(int i=head[id];i!=-1;i=eg[i].next)
        if(eg[i].to!=fa)
            pre[id]+=calcpre(eg[i].to,id);
    pre[id]+=mark[id];
    return pre[id];
}
bool judge(int x)
{
    int num=0;
    for(int i=1;i<=m;i++)
    {
        if(p[i].len>x)
        {
            mark[p[i].a]++;
            mark[p[i].b]++;
            mark[p[i].lc]-=2;
            num++;
        }
    }
    if(num==0)return true;
    calcpre(1,1);
    int MAX=-1;
    for(int i=1;i<=n;i++)
    {
        if(pre[i]==num)
            MAX=max(MAX,val[i]);
        mark[i]=0;
    }
    if(maxlen-MAX<=x)return true;
    return false;
}
int main()
{
    int a,b,t;
    n=read();m=read();
    top=0;
    memset(head,-1,sizeof(head));
    for(int i=0;i<n-1;i++)
    {
        a=read();b=read();t=read();
        add(a,b,t);add(b,a,t);
    }
    cnt=0;
    dfs1(1,1,1,0);
    dfs2(1,1);
    maxlen=-1;
    for(int i=1;i<=m;i++)
    {
        p[i].a=read();p[i].b=read();
        p[i].lc=lca(p[i].a,p[i].b);
        p[i].len=dis[p[i].a]+dis[p[i].b]-2*dis[p[i].lc];
        maxlen=max(maxlen,p[i].len);
    }
    int l=0,r=maxlen,ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(judge(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

已知路径求树上所有节点被路径覆盖次数

对每条路径的起点a和终点b的权值+1 , 对lca(a, b)的权值-1 , 对lca(a,b)的父节点权值-1。

从根节点开始深搜，回溯时将其本身的权值加上所有子节点的权值。

每个节点的权值即是其被路径覆盖的次数。

例题：

P3258

给出一棵树，以及访问结点的顺序，问每个结点要访问几次，访问最后一个结点不算。

思路：裸题。

代码：

int a[300010];
vector<int>v[300010];
int par[300010];
int dep[300010];
int tot[300010];
int son[300010];
int top[300010];
int idx[300010];
int mark[300010];
int ans[300010];
int cnt;
int dfs1(int id,int fa,int depth)
{
    par[id]=fa;
    dep[id]=depth;
    int maxson=-1;
    son[id]=0;
    int len=v[id].size();
    for(int i=0;i<len;i++)
    {
        int temp=v[id][i];
        if(temp==fa)continue;
        tot[id]+=dfs1(temp,id,depth+1);
        if(tot[temp]>maxson)
        {
            son[id]=temp;
            maxson=tot[temp];
        }
    }
    return tot[id];
}
void dfs2(int id,int topf)
{
    idx[id]=++cnt;
    top[id]=topf;
    if(son[id]==0)return;
    dfs2(son[id],topf);
    int len=v[id].size();
    for(int i=0;i<len;i++)
    {
        int temp=v[id][i];
        if(idx[temp]==0)dfs2(temp,temp);
    }
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=par[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
int dfs(int id,int fa)
{
    int len=v[id].size();
    ans[id]=mark[id];
    for(int i=0;i<len;i++)
    {
        int temp=v[id][i];
        if(temp==fa)continue;
        ans[id]+=dfs(temp,id);
    }
    return ans[id];
}
int main()
{
    int n,x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    memset(idx,0,sizeof(idx));
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs1(1,0,1);
    cnt=0;
    dfs2(1,0);
    for(int i=1;i<n;i++)
    {
        mark[a[i]]++;
        mark[a[i+1]]++;
        int lc=lca(a[i],a[i+1]);
        mark[lc]--;
        mark[par[lc]]--;
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
    {
        if(i==a[1])printf("%d\n",ans[i]);
        else printf("%d\n",ans[i]-1);
    }
    return 0;
}