LOJ6210 「美团 CodeM 决赛」tree

Link
不难发现最优解中最多经过一个点权为(2)的点，其余的点点权都为(1)。
直接树形dp即可。

#include<cctype>
#include<cstdio>
#include<vector>
#include<algorithm>
const int N=2000007;
char ibuf[1<<24|1],*iS=ibuf;int n,mn=1e9,s1,s2,a[N],f[N][2];std::vector<int>e[N];
int read(){int x=0;while(isspace(*iS))++iS;while(isdigit(*iS))(x*=10)+=*iS++&15;return x;}
void dfs(int u,int fa)
{
    if(a[u]==1) f[u][0]=1; else if(a[u]==2) f[u][1]=1;
    for(int v:e[u])
    {
	if(v==fa) continue;
	dfs(v,u),s1=std::max(s1,f[u][0]+f[v][0]),s2=std::max(s2,std::max(f[u][1]+f[v][0],f[u][0]+f[v][1]));
	if(a[u]==1) f[u][0]=std::max(f[u][0],f[v][0]+1),f[u][1]=std::max(f[u][1],f[v][1]+1);
	else if(a[u]==2) f[u][1]=std::max(f[u][1],f[v][0]+1);
    }
}
int main()
{
    fread(ibuf,1,1<<24,stdin),n=read();
    for(int i=1,u,v;i<n;++i) u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
    for(int i=1;i<=n;++i) mn=std::min(mn,a[i]=read());
    if(mn^1) return !printf("%d/1
",mn);
    dfs(1,0),s2<=2*s1? printf("1/%d
",s1):printf("%d/%d
",s2&1? 2:1,s2/(s2&1? 1:2));
}