题意:

给你个n个点的树

某些边反向走是违法的,第一次罚款1个单位,第二次2个,以此类推

你需要从1号点出发,以此走过K个点

问最终被罚款多少 (对1e9+7取模)

解法1:树链剖分大法好!

然而TLE了...

解法2:这时候就要LCA了

LCA求出每个点向上多少次,向下多少次

当然向上是直接计算到根,向下是从根到它..

所以就要..a-->b可以理解为a-->root一次以及b-->root负一次.....

最后求出每条路到底被经过了多少次即可..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int maxn=100005;
int go_up[maxn];
int go_down[maxn];
int up[100005][25];
int unok[100005][2];
struct edge
{
    int y;
    int weight;
    edge * next;
};
edge * li[100005];
edge * new_edge()
{
    static edge a[200005];
    static int top=0;
    return &a[top++];
}
void inserts(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y,int z)
{
    inserts(x,y,0);
    inserts(y,x,z); 
}
int father[100005];
int depth[100005];
void dfs(int x)
{
    edge * t;
    int i;
    up[x][0]=father[x];
    for (i=1;i<20;i++)
    {
        if (up[x][i-1]==-1)
        {
            up[x][i]=-1;
        }
        else
        {
            up[x][i]=up[up[x][i-1]][i-1];
        }
    }
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x])
        {
            unok[x][1]=t->weight;
            continue;
        }
        father[t->y]=x;
        depth[t->y]=depth[x]+1;
        unok[t->y][0]=t->weight;
        dfs(t->y);
    }
}
void dfs2(int x)
{
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x]) continue;
        dfs2(t->y);
    }
    if (x!=0)
    {
        go_up[father[x]]+=go_up[x];
        go_down[father[x]]+=go_down[x];
    }
}
int lca(int x,int y)
{
    if (depth[x]<depth[y]) swap(x,y);
    int t=depth[x]-depth[y];
    int i;
    for (i=20;i>=0;i--)
    {
        if ((1<<i)&t) x=up[x][i];
    }
    if (x==y) return x;
    for (i=20;i>=0;i--)
    {
        if (up[x][i]!=up[y][i])
        {
            x=up[x][i];
            y=up[y][i];
        }
    }
    return father[x];
}
int power2[1000005];
const int modo=1000000007;
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    for (i=1;i<=1000001;i++)
    {
        power2[i]=(power2[i-1]<<1)+1;
        power2[i]%=modo;
    }
    for (i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        x--;
        y--;
        insert_edge(x,y,z);
    }
    father[0]=-1;
    depth[0]=0;
    dfs(0);
    int past=0;
    int m;
    scanf("%d",&m);
    for (i=0;i<m;i++)
    {
        int now;
        scanf("%d",&now);
        now--;
        int z=lca(now,past);
        go_up[z]--;
        go_down[z]--;
        go_up[past]++;
        go_down[now]++;
        past=now;
    }
    dfs2(0);
    int ans=0;
    for (i=0;i<n;i++)
    {
        if (unok[i][0]) ans+=power2[go_down[i]];
        ans%=modo;
        if (unok[i][1]) ans+=power2[go_up[i]];
        ans%=modo;
    }
    printf("%d\n",ans);
    return 0;
}