[CF575B]Bribes
题目大意:
一棵\(n(n\le10^5)\)个结点的树,有些边有方向,对于每条边,如果第\(i\)次逆向走过这条边,就会产生\(2^{i-1}\)的代价。开始在\(1\)号点,依次经过给出的\(m(m\le10^6)\)个点,求总代价最小值。
思路:
维护树上差分即可。
源代码:
#include<cstdio>
#include<cctype>
#include<vector>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=1e5+1,mod=1e9+7;
inline int power(int a,int k) {
int ret=1;
for(;k;k>>=1) {
if(k&1) ret=1ll*ret*a%mod;
a=1ll*a*a%mod;
}
return ret;
}
std::vector<int> e[N];
inline void add_edge(const int &u,const int &v) {
e[u].push_back(v);
e[v].push_back(u);
}
struct Edge {
int u,v;
bool t;
};
Edge edge[N];
int dep[N],par[N],son[N],size[N],top[N],d[2][N];
void dfs(const int &x,const int &par) {
size[x]=1;
::par[x]=par;
dep[x]=dep[par]+1;
for(unsigned i=0;i<e[x].size();i++) {
const int &y=e[x][i];
if(y==par) continue;
dfs(y,x);
size[x]+=size[y];
if(size[y]>size[son[x]]) {
son[x]=y;
}
}
}
void dfs(const int &x) {
top[x]=x==son[par[x]]?top[par[x]]:x;
if(son[x]) dfs(son[x]);
for(unsigned i=0;i<e[x].size();i++) {
const int &y=e[x][i];
if(y==par[x]||y==son[x]) continue;
dfs(y);
}
}
inline int lca(int x,int y) {
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) {
std::swap(x,y);
}
x=par[top[x]];
}
if(dep[x]<dep[y]) std::swap(x,y);
return y;
}
void solve(const int &x) {
for(unsigned i=0;i<e[x].size();i++) {
const int &y=e[x][i];
if(y==par[x]) continue;
solve(y);
d[0][x]+=d[0][y];
d[1][x]+=d[1][y];
}
}
int main() {
const int n=getint();
for(register int i=1;i<n;i++) {
edge[i].u=getint();
edge[i].v=getint();
edge[i].t=getint();
add_edge(edge[i].u,edge[i].v);
}
dfs(1,0);
dfs(1);
const int m=getint();
for(register int i=0,s=1;i<m;i++) {
const int t=getint();
const int u=lca(s,t);
d[0][s]++;
d[0][u]--;
d[1][t]++;
d[1][u]--;
s=t;
}
solve(1);
int ans=0;
for(register int i=1;i<n;i++) {
if(!edge[i].t) continue;
const int &u=edge[i].u,&v=edge[i].v;
const int tmp=dep[u]<dep[v]?d[0][v]:d[1][u];
(ans+=(power(2,tmp)+mod-1)%mod)%=mod;
}
printf("%d\n",ans);
return 0;
}