一、常见套路
重链重儿子启发式，倍增，树上可持久单调链栈。
dfs序。树上差分。线段树合并。
考虑每条边的贡献。
换根：1、换根DP，2、考虑根在lca内外。
图转化为树，考虑树边非树边贡献。树边非树边反祖边。最小路径树。
询问离线。每次重新做。
一表达式：
天天爱跑步：树上差分。
w[x]+deep[x]=deep[u]，
deep[u]-2*deep[LCA]+deep[x]=w[x]）
最短路：（最短路树）树剖/并查集。
非树边（u，v）对节点x影响：dis(v)+dis(u)+len(v,u)-dis(x) （x在u,v到lca的两条链上）
树剖更新链。
或排序后并查集维护已经更新过的段。使每个点只被最小权更新一次。
测试94：射手座之日：线段树合并+线段树维护区间左右端点及信息。
(w[x]-w[f[x]])*sigma::(ri-li+1)(ri-li+2)/2
(只考虑自己子树内部区间贡献。但是要减去父亲的。差分思想。)
一树上匹配问题：
优先子树内部。
二、数据结构
树剖，并查集。
线段树合并。
三、树DP
1、子树合并：用子树信息更新过程中的变量，一般用辅助数组。或倒着转移。
T：测试53 T3：
这题辅助数组和DP数组含义不一样。DP数组要统计奇偶度数点个数，辅助数组是讨论当前点度数奇偶性。
再根据奇偶性讨论当前点对DP数组奇点数是否有贡献。
关于状态定义：奇偶是与szn相似的思路。奇点必然是端点。相当于讨论是否为端点。
由于起点终点不好区分，所以用奇偶性讨论路径条数。
#include<bits/stdc++.h> #define F(i,a,b) for(int i=a;i<=b;++i) #define LL long long #define pf(a) printf("%d ",a) #define PF(a) printf("%lld ",a) #define phn puts("") using namespace std; int read(); typedef pair<int,int> pir; int n; #define N 200010 int to[N<<1],fir[N<<1],head[N],kd[N<<1],dm[N<<1],cnt; void add(int x,int y,int KD,int DM){to[++cnt]=y;fir[cnt]=head[x];head[x]=cnt;kd[cnt]=KD;dm[cnt]=DM;} pir f[N][2]; const int inf=1e8; #define mp(a,b) make_pair(a,b) #define ft first #define sd second inline pir operator+(const pir&a,const pir&b){ return mp(a.ft+b.ft,a.sd+b.sd); } inline int operator<(const pir&a,const pir&b){ return a.ft<b.ft||(a.ft==b.ft&&a.sd<b.sd); } inline pir min(const pir&a,const pir&b){ return a<b?a:b; } void dfs(int x,int fa,int b){ pir w[2][2]={mp(0,0),mp(inf,inf),mp(0,0),mp(inf,inf)}; /** ??*/ int p=0; for(int i=head[x],v=to[i];i;i=fir[i],v=to[i])if(v!=fa){ p^=1; dfs(v,x,i); w[p][0]=min(w[!p][0]+f[v][0],w[!p][1]+f[v][1]); w[p][1]=min(w[!p][0]+f[v][1],w[!p][1]+f[v][0]); } f[x][0]=min(w[p][0],mp(w[p][1].ft+1,w[p][1].sd)); f[x][1]=min(mp(w[p][1].ft,w[p][1].sd+1),mp(w[p][0].ft+1,w[p][0].sd+1)); if(kd[b]==dm[b]){ f[x][1]=mp(inf,inf); } else if(kd[b]!=dm[b]&&dm[b]!=2){ f[x][0]=mp(inf,inf); } } int main(){ n=read(); F(i,1,n-1){ int a=read(),b=read(),c=read(),d=read(); add(a,b,c,d);add(b,a,c,d); } // memset(f,0x2f,sizeof(f)); dfs(1,0,0); printf("%d %d ",f[1][0].ft/2,f[1][0].sd); } int read(){ int s=0,f=0;char ch; while(ch=getchar(),ch=='-'?f=1:0,!isdigit(ch)); for(;isdigit(ch);s=s*10+(ch^48),ch=getchar()); return f?-s:s; } /* g++ 3.cpp -g ./a.out 6 1 3 0 1 1 2 0 2 2 4 1 0 4 5 1 0 5 6 0 2 9 1 3 0 2 1 2 0 2 2 4 1 0 4 5 1 0 5 6 0 2 2 7 1 2 4 8 1 0 7 9 0 1 5 2 1 1 0 1 3 0 1 2 4 1 2 5 2 1 1 3 1 3 1 2 2 1 0 0 */