树形dp Civilization QBXT Test Ⅱ T3

题意：一棵树，$q$次询问，每次给出一个点$x$，求到该点距离为奇数的节点的距离和与到该点距离为偶数的节点的距离和。

比较明显的树形dp，但是我不会QAQ。 首先先考虑求树上所有点到一个点距离之和，我们使用两遍$dfs$完成，我们设$f[x]$表示$x$的子树中所有点到该点的距离之和，$siz[x]$表示以$x$为根的子树大小，在第一遍$dfs$中，我们用子节点去更新父节点，转移：$$siz[x]+=siz[v]$$$$f[x]=f[v]+e[i].dis\ast siz[v]$$

设$ans[x]$表示节点$x$的答案，如果以$1$为根的话则$ans[1]=f[1]$。在第二遍$dfs$中，我们用父节点去更新子节点，转移：$$ans[v]=ans[x]-e[i].dis\ast siz[v]+e[i].dis\ast (n-siz[v])$$

这个问题就被解决了，然后考虑原问题，我们发现二者非常类似，只需要将奇数和偶数分开来算即可。

我们设$f[x][0/1]$表示$x$的子树中所有点到该点的距离为偶数/奇数之和，$ans[x][0/1]$表示距离$x$为偶数/奇数的答案，$siz1[x][0/1]$表示以$x$为根的子树中到$x$点为偶数/奇数的点的数量，$siz2[x][0/1]$表示全树中距离点$x$为偶数/奇数的点的数量。

在$dfs$中，如果该边为奇数，则到这个点的距离的奇偶性就会改变，如果该边为偶数，则不会改变。转移方程类似上面的，只不过要分奇偶讨论。转移方程在代码里，比较清楚。

#include<iostream> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=2e5+10; int siz1[maxn][2],siz2[maxn][2]; ll ans[maxn][2],f[maxn][2]; int head[1001000],num,n,q; struct node { int next,to,dis; }e[1001000]; void add(int from,int to,int dis) { e[++num].next=head[from]; e[num].to=to; e[num].dis=dis; head[from]=num; } void dfs1(int x,int fa) { siz1[x][0]=1; for(int i=head[x];i;i=e[i].next) { int v=e[i].to; if(v!=fa) { dfs1(v,x); if(e[i].dis%2==1) { siz1[x][0]+=siz1[v][1]; siz1[x][1]+=siz1[v][0]; f[x][0]+=f[v][1]+e[i].dis*siz1[v][1]; f[x][1]+=f[v][0]+e[i].dis*siz1[v][0]; } else { siz1[x][0]+=siz1[v][0]; siz1[x][1]+=siz1[v][1]; f[x][0]+=f[v][0]+e[i].dis*siz1[v][0]; f[x][1]+=f[v][1]+e[i].dis*siz1[v][1]; } } } } void dfs2(int x,int fa) { for(int i=head[x];i;i=e[i].next) { int v=e[i].to; if(v!=fa) { if(e[i].dis%2==1) { siz2[v][1]=siz2[x][0]; siz2[v][0]=siz2[x][1]; ans[v][1]=ans[x][0]-e[i].dis*siz1[v][1]+e[i].dis*(siz2[x][0]-siz1[v][1]); ans[v][0]=ans[x][1]-e[i].dis*siz1[v][0]+e[i].dis*(siz2[x][1]-siz1[v][0]); } else { siz2[v][1]=siz2[x][1]; siz2[v][0]=siz2[x][0]; ans[v][1]=ans[x][1]-e[i].dis*siz1[v][1]+e[i].dis*(siz2[x][1]-siz1[v][1]); ans[v][0]=ans[x][0]-e[i].dis*siz1[v][0]+e[i].dis*(siz2[x][0]-siz1[v][0]); } dfs2(v,x); } } } int main() { freopen("civilization.in","r",stdin); freopen("civilization.out","w",stdout); cin>>n>>q; for(int i=1;i<=n-1;++i) { int x,y,d; scanf("%d%d%d",&x,&y,&d); add(x,y,d); add(y,x,d); } dfs1(1,0); siz2[1][1]=siz1[1][1]; siz2[1][0]=siz1[1][0]; ans[1][1]=f[1][1]; ans[1][0]=f[1][0]; dfs2(1,0); for(int i=1;i<=q;++i) { int x; scanf("%d",&x); printf("%lld %lld\n",ans[x][1],ans[x][0]); } return 0; }